[브루트포스, 백트래킹] 백준 - N과 M (4)

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

-문제해설

1. n, m, arr, sb는 모두 전역변수, n과 m을 입력받는다.

 

2. dfs메소드 호출. dfs 매개변수는 arr배열에 어느 수부터 저장할 지를 나타내는 start와 dfs메서드의 재귀호출한 횟수(깊이)를 나타내는 depth가 있다.

 

3. dfs메소드 내부에는 

depth == m일 경우 arr배열에 담겨있는 값들을 sb에 append시키고 메서드를 return시켜서 이전 dfs 메서드로 돌아간다.

 

depth != m이라면 for문에서 i=start 부터 i <= n까지 반복하면서

arr[depth] = i 값을 담아주고 dfs( i, depth+1 ) 호출한다.

 

4. 최종적으로 sb를 출력하면 정답이다.

 

 

 

 

파이썬의 경우

itertools 모듈에 값의 중복을 포함한 조합을 만들어주는 combinations_with_replacement라는 메서드를 사용하면 쉽게구현이 가능하다.

 

 

-자바

package bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ15652 {
	static int n, m;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	
	public static void dfs( int start, int depth ) {
		if( depth == m ) {
			for( int val : arr ) sb.append( val ).append( " " );
			sb.append( "\n" );
			return;
		}
		
		for( int i=start; i<=n; i++ ) {
			arr[depth] = i;
			dfs( i, depth+1 );
		}
	}
	
	public static void main( String[] args ) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		
		arr = new int[m];
		dfs( 1, 0 );
		
		System.out.println( sb );
	}
}

 

-파이썬

from sys import stdin
from itertools import combinations_with_replacement

input = stdin.readline
n, m = map(int, input().split())
print( '\n'.join( map(' '.join, combinations_with_replacement( map(str, range(1, n+1)), m ) ) ) )