[백준] 15651번 : N과 M (3)

문제

n과 m이 주어졌을 때 (1 <= m <= n <= 7),

1 ~ n까지의 수를 가지고 중복으로 사용하여 만들 수 있는

모든 m의 자리의 수를 출력하라

접근 방식

재귀를 이용한 백트래킹을 연습하기 좋은 문제라 N과 M 시리즈를 모두 풀어보려 한다.

1번과 2번도 좋은 문제이기에 재귀와 백트래킹이 아직 익숙하지 않은 사람들은

꼭 풀어보면 좋을 거 같다.

 

늘 그렇듯 규칙이 존재하는 문제라면 첫 재귀의 동작까지만 구현한 후에

컴퓨터를 믿고 맡기면 된다.

 

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

 

이번 문제에서는 위와 깊이 출력 예제 중 가장 간단한 경우에 대해서만

재귀 로직을 구현하기만 하면 된다.

 

n과 m 시리즈의 1번과 2번 문제를 풀어본 사람이라면

이번 문제는 엄청 쉽게 느껴질텐데 3번 문제는 숫자의 중복을 허용하기 때문에

기존과 다르게 숫자의 사용 여부를 체크할 필요가 없다.

 

그냥 매 재귀 호출마다 1부터 n까지 반복하는 반복문을 돌면서

기저 조건을 현재 저장한 숫자의 개수가 m개인지 확인하고

탈출하게만 하면 끝이다.

 

풀이

public class Main {

	private static int n;
	private static int m;
	private static StringBuilder sb = new StringBuilder();
	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);

		System.out.println(sb);
	}

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

			return;
		}

		int start = 1;

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