📌 문제 : (2)
자연수
N과M이 주어졌을 때, 아래 조건을 만족하는 길이가M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터
N까지 자연수 중에서 중복 없이M개를 고른 수열- 고른 수열은 오름차순이어야 한다.
⬇️ 입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
⬆️ 출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
💡 코드 : (2)
✅ 이번 문제들은 이전 문제 응용 버전이라고 보면 된다! 이전 문제는 무조건 수열에 대한 조건이 없었다면, 이번 문제는 수열이 오름차순 정렬이여야 한다는 조건이 더 붙었다.
이전 문제에서는dfs()를 호출할 때 단계depth(=idx)만 입력받았는데, 이번 문제는 다음 단계의 수가 앞 단계보다 커야하므로 이번 단계에서 시작 가능한 수num을 추가로 입력받는다.
main에서dfs(0, 1)을 호출했다면 가장 첫 단계는 1부터 시작할 수 있다는 뜻이고, 재귀 함수를 통해dfs(1, 2)를 호출했다면 다음 단계는 이전 단계의 수인 1을 제외한 2부터 시작할 수 있다는 뜻이다. 즉, 다음 단계에 대한 재귀 함수를 호출할 때마다 시작 가능한num을 1씩 증가시켜주면 된다.
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int[] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[m];
dfs(0, 1);
bw.write(sb + "");
br.close();
bw.close();
}
static void dfs(int depth, int num) {
if(depth == m) {
for(int i=0;i<m;i++) {
sb.append(arr[i]).append(" ");
}
sb.append("\n");
return;
}
for(int i=num;i<=n;i++) {
arr[depth] = i;
dfs(depth+1, i+1);
}
}
}
📌 문제 : (3)
자연수
N과M이 주어졌을 때, 아래 조건을 만족하는 길이가M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터
N까지 자연수 중에서M개를 고른 수열- 같은 수를 여러 번 골라도 된다.
⬇️ 입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
⬆️ 출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
💡 코드 : (3)
✅ 이번 문제는 수열에 중복된 수가 존재해도 된다는 조건이 붙었다.
이는isUsed[]를 통해 해당 수를 사용했는지 판단할 필요도, 오름차순 정렬을 위해 시작 가능한 수num을 정의할 필요도 없이 단순하게 다음 단계만 호출해주면 된다!
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int[] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[m];
dfs(0);
bw.write(sb + "");
br.close();
bw.close();
}
static void dfs(int depth) {
if(depth == m) {
for(int i=0;i<m;i++) {
sb.append(arr[i]).append(" ");
}
sb.append("\n");
return;
}
for(int i=1;i<=n;i++) {
arr[depth] = i;
dfs(depth+1);
}
}
}
📌 문제 : (4)
자연수
N과M이 주어졌을 때, 아래 조건을 만족하는 길이가M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터
N까지 자연수 중에서M개를 고른 수열- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가
A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
⬇️ 입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
⬆️ 출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
💡 코드 : (4)
✅ 이번 문제는 단순 오름차순이 아닌 이전 단계의 수보다 크거나 같은 수만 올 수 있는 경우이다. 이전 단계의 수보다 큰 수만 올 수 있었던 (2)번 코드와 유사하므로 이를 살짝만 수정해서 해결했다!
(2)번 문제에서num은 이전 단계에서 사용한 수보다 큰 수만 올 수 있었기 때문에 재귀함수를 호출할 때i+1을 넘겨줬는데, 이번 문제에서는 크거나 같은 수를 허용하므로i를 그대로 넘겨주면 된다.
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static boolean[] isUsed;
static int[] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
isUsed = new boolean[n+1];
arr = new int[m];
dfs(0, 1);
bw.write(sb + "");
br.close();
bw.close();
}
static void dfs(int depth, int num) {
if(depth == m) {
for(int i=0;i<m;i++) {
sb.append(arr[i]).append(" ");
}
sb.append("\n");
return;
}
for(int i=num;i<=n;i++) {
arr[depth] = i;
dfs(depth+1, i);
}
}
}
