IT/알고리즘

백준15652 n과m(4)

어센트 2020. 3. 19. 16:32

https://www.acmicpc.net/problem/15652

 

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

 

처음 호출되거나 선택할 예정인 숫자가 이전에 선택했던 숫자이상이면 선택하고 함수를 호출하는 방식으로 문제를 해결했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package 백트래킹;
 
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class N과M_4 {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader( System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[m];
        Arrays.fill(arr,-1);
       fun(n,m,arr,0,0);
        System.out.println(sb);
    }
    static  void fun(int n,int m,int[] ar,int depth,int size){
        if(size==m){
            for(int i:ar){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        if(depth==n){
            return;
        }
        for (int i = 0; i <n ; i++) {
            if(size==0 || ar[size-1]<=i+1){ //처음 호출되거나 선택할 숫자가 이전에 선택한것 이상이라면 추가
                ar[size] = i+1;
                fun(n,m,ar,depth+1,size+1);
            }
        }
    }
}
 
cs