문제

이해

49이하의 자연수 중에서 k개의 수를 뽑아 이중에서 6개의 수로 조합가능한 경우를 모두 출력하는 문제이다.

접근

간단하게 조합의 경우를 출력하는 문제이다. 조합식 kC6의 개수를 출력하면 된다.

조합의 경우에는 단순 bfs로 해결할 수 있다.

단, 조합은 순서를 생각하지 않기 때문에 중복인 경우를 제외하면서 오름차순으로 출력해야 한다.

이 부분은 재귀 bfs 함수에 파라미터로 이전에 뽑았던 수의 번호를 넣어주면 된다.

다음 수를 뽑을 땐 이전에 뽑았던 수의 번호보다 큰 범위에서 뽑으면 중복을 제거할 수 있다.

코드

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob6603 {
    static int[] numbers;
    static boolean[] visited;
    static int k;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());

            k = Integer.parseInt(st.nextToken());

            if(k == 0){
                break;
            }

            numbers = new int[k];
            visited = new boolean[k];
            for(int i=0;i<k;i++){
                numbers[i] = Integer.parseInt(st.nextToken());
            }

            bfs(0, -1);

            System.out.println();
        }
    }    

    static void bfs(int depth, int prev_index){
        if(depth == 6){
            for(int i=0;i<k;i++){
                if(visited[i]){
                    System.out.print(numbers[i] + " ");
                }
            }
            System.out.println();

            return;
        }

        for(int i=prev_index+1;i<k;i++){
            visited[i] = true;
            bfs(depth + 1, i);
            visited[i] = false;
        }
    }
}

결과