6603번 : 로또

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

6603번: 로또

 

문제

 

입력

 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int k;
    static StringBuilder sb;
    static int[] s;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        sb = new StringBuilder();

        while (true) {
            st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());
            if(k == 0) break;
            s = new int[k + 1];

            for (int i = 1; i <= k; i++) {
                s[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(s);
            backtrack(0, "", 0);
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static void backtrack(int cnt, String str, int pre) {
        if (cnt == 6) {
            sb.append(str.trim() + "\n");
            return;
        }

        for (int i = pre + 1; i <= k; i++) {
            backtrack(cnt + 1, str + " " + s[i], i);
        }
    }

}

 

해결방법

백 트래킹으로 풀 수 있는 문제이다.

로또 번호를 사전순으로 출력한다. 정렬을 해야 한다.

 

독알 로또는 수 6개를 사용한다. 로또 번호가 6개라면 Stringbuilder에 해당 문지열을 추가한다.