https://www.acmicpc.net/problem/15652
15652번: N과 M (4)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
<문제 요약>
1~N 사이의 수를 M개 고른 수열
같은 수를 여러번 골라도 되지만 순서는 비내림차순이어야한다.
<문제 풀이>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class P15652 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
arr=new int[M];
dfs(0,1);
System.out.println(sb);
}
static int N;
static int M;
static int[] arr;
static StringBuilder sb=new StringBuilder();
static void dfs(int depth,int num){
if(depth==M){
for(int val:arr) sb.append(val).append(" ");
sb.append("\n");
return;
}
for(int i=num;i<=N;i++){
arr[depth]=i;
dfs(depth+1,i);
}
}
}
문제에서 비내림차순이라길래
오름차순과 같은 말일까 생각했는데 다른 개념인 것 같다
| 오름차순 예시 | 비내림차순 예시 |
| 1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 |
1 1 1 1 1 2 1 1 3 1 2 2 1 2 3 |
이런문제는 순서 여부, 중복 허용 여부 등과 같은 조건을 잘보고 풀이를 생각해봐야할 것 같다
전체적인 틀은 비슷하지만 조건에 따라 내용은 약간씩 다른 느낌?
