[백준] 15652번 : N과 M (4)

문제

 

 

접근 방식

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

 

우선 1부터 N까지의 숫자를 중복이 가능하게 3개를 뽑아서 수열을 만들 수 있을 때

위와 같은 규칙대로 수열을 만들어야 한다.

 

111, 112, 113 >> 122, 123

 

위의 숫자를 보면 규칙을 하나 찾을 수 있는데

다음에 올 수 있는 숫자의 범위는

항상 이전의 숫자보다 같거나 커야 한다.

 

별 찍기도 그렇고 N과 M시리즈도 그렇고

혼자 규칙 찾아서 풀어야 하는거만 빼면

재귀 연습하기는 참 좋긴하다...

 

어쨋든 이 규칙대로 수열을 만들기 위해서는

재귀 호출을 할 때 다음에 올 숫자의 시작 범위를

파라미터로 넘겨줘야 한다는 것이다.

 

이 부분만 생각하면서 풀면 어렵지 않게 풀 수 있는데

규칙을 잘못 알아서 삽질을 했던 문제다...

 

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] nm = br.readLine().split(" ");

		n = Integer.parseInt(nm[0]);
		m = Integer.parseInt(nm[1]);

		arr = new int[m];

		makeNumber(0, 1);

		System.out.println(sb);
	}

	private static void makeNumber(int size, int start) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(arr[i]).append(" ");
			}

			sb.append("\n");

			return;
		}

		for (int i = start; i <= n; i++) {
			arr[size] = i;
			makeNumber(size + 1, i);
		}
	}
}