💁15651번. N과 M (3)
https://www.acmicpc.net/problem/15651
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력 1
3 1예제 출력 1
1 2 3예제 입력 2
4 2예제 출력 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예제 입력 3
3 3예제 출력 3
1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 2 3 1 2 3 2 2 3 3 3 1 1 3 1 2 3 1 3 3 2 1 3 2 2 3 2 3 3 3 1 3 3 2 3 3 3
풀이
import java.util.Scanner;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] selected;
// Recurrence Function (재귀 함수)
// 만약 M개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것
// 아직 M개를 고르지 않음 => k번째부터 M번쨰 원소를 조건에 맞게 고르는 방법을 시도한다
private static void rec_func(int k) {
if(k == M + 1) { // 다 골랐다
// selected[1...M] 배열이 새롭게 탐색된 결과
for(int i=1; i<=M; i++){
sb.append(selected[i]).append(' ');
}
sb.append('\n');
} else {
// 1~N 까지를 k번 원소로 한 번씩 정하고,
// 매번 k+1 번부터 M번 원소로 재귀호출 해주기
for (int cand = 1; cand <= N; cand++) {
selected[k] = cand;
rec_func(k + 1);
selected[k] = 0;
}
}
}
public static void main(String[] args) {
input();
// 1번째 원소부터 M번째 원소를 조건에 맞는 모든 방법을 찾아줘
rec_func(1);
System.out.println(sb.toString());
}
private static void input() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
selected = new int[M + 1];
}
}
완전탐색
재귀함수 돌리고 돌리고
💁 15652번. N과 M (4)
위의 문제와 흡사하나 비내림차순이어야 한다.
https://www.acmicpc.net/problem/15652
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력 2
4 2예제 출력 2
1 1 1 2 1 3 1 4 2 2 2 3 2 4 3 3 3 4 4 4예제 입력 3
3 3예제 출력 3
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
풀이
// 생략 코드는 15651번 풀이 참고
private static void rec_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(" ");
}
sb.append("\n");
} else {
int start = selected[k-1];
if(start == 0) start = 1;
for (int cand = start; cand <= N; cand++) {
selected[k] = cand;
rec_func(k + 1);
selected[k] = 0;
}
}
}
selected[k-1]
selected 배열에 순차적으로 값을 추가할때,
이전에 쓰였던 숫자인 selected[k-1] 값보다는 크거나 같아야 하기 때문에
이 숫자를 for문의 start로 잡는다.
💁 15650번. N과 M (2)
오름차순
https://www.acmicpc.net/problem/15650
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3예제 입력 2
4 2
예제 출력 2
1 2
1 3
1 4
2 3
2 4
3 4예제 입력 3
4 4
예제 출력 3
1 2 3 4
풀이
// 생략 코드는 15651번 풀이 참고
private static void rec_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(" ");
}
sb.append("\n");
} else {
for (int cand = selected[k-1] + 1; cand <= N; cand++) {
selected[k] = cand;
rec_func(k + 1);
selected[k] = 0;
}
}
}selected[k-1] + 1
candidate 의 시작값이 1이 아니라, 이 전에 쓰였던 숫자보다 하나 큰 숫자부터 시작을 한다.
