[백준][6603번] 로또

문제 URL

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

나의 풀이 (재귀)

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] ans = new int[6];
    // input
    static int[] w = new int[13];

    public static void main(String[] args) throws IOException {
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken());
            if (size == 0) {
                return;
            }
            for (int i = 0; i < size; i++) {
                w[i] = Integer.parseInt(st.nextToken());
            }
            cal(0, 0, size, 6);
            bw.newLine();
            bw.flush();
        }
    }
    /*
    idx : 탐색중인 인덱스
    selected : 선택된 개수
    n: idx의 전체 size
    m: 조합을 만들고자 하는 개수
    */
    public static void cal(int idx, int selected, int n, int m) throws IOException {
        if (selected == m) {
            StringBuilder sb =new StringBuilder();
            for(int i=0; i<6; i++){
                sb.append(w[ans[i]]+" ");
            }
            bw.write(sb.toString());
            bw.newLine();
            return;
        }

        if (idx >= n)
            return;

        ans[selected] = idx;
        cal(idx+1, selected+1, n, m);
        ans[selected] = 0;
        cal(idx+1, selected, n, m);
    }
}

다른 풀이 (순열)

순열을 이용한 풀이방식이다. 이 문제는 전에 풀었던 순열문제와 다르게 순서가 중요하지않는 조합문제다. 하지만 다르게 생각해서 순열을 이용해서 풀수있다.

---

전체를 k라고 하자 고르는것을 1이라하면 6개를 고르면되고 안고름을 0이라고하면 k-6개을 고르면된다.

다시말해, 0을 k-6개, 1을 6개 넣은 다음에 next_permutation(다음수열 함수)를 수행하면 조합 모든 조합을 구할수있다.

import java.util.*;
public class Main {
    static boolean next_permutgetion(int[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length-1;
        while (a[j] <= a[i-1]) {
            j -= 1;
        }

        int temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) break;
            int[] a = new int[n];
            for (int i=0; i<n; i++) {
                a[i] = sc.nextInt();
            }
            int[] d = new int[n];
            for (int i=0; i<n; i++) {
                if (i < n-6) d[i] = 0;
                else d[i] = 1;
            }
            ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
            do {
                ArrayList<Integer> cur = new ArrayList<>();
                for (int i=0; i<n; i++) {
                    if (d[i] == 1) {
                        cur.add(a[i]);
                    }
                }
                ans.add(cur);
            } while (next_permutgetion(d));
            Collections.sort(ans, new Comparator<ArrayList<Integer>>() {
                public int compare(ArrayList<Integer> l1, ArrayList<Integer> l2) {
                    int n = l1.size();
                    int m = l2.size();
                    int i = 0;
                    while (i < n && i < m) {
                        int t1 = l1.get(i);
                        int t2 = l2.get(i);
                        if (t1 < t2) return -1;
                        else if (t1 > t2) return 1;
                        i += 1;
                    }
                    if (i == n && i != m) return -1;
                    else if (i != n && i == m) return 1;
                    return 0;
                }
            });
            for (ArrayList<Integer> v : ans) {
                for (int x : v) {
                    System.out.print(x + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}