728x90
문제
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);
}
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 15654번 : N과 M (5) (0) | 2023.10.29 |
---|---|
[백준] 15652번 : N과 M (4) (0) | 2023.10.29 |
[백준] 2448번 : 별 찍기 - 11 (0) | 2023.10.27 |
[백준] 2447번 : 별 찍기 - 10 (0) | 2023.10.27 |
[백준] 1992번 : 쿼드트리 (0) | 2023.10.26 |