[알고리즘] 백준 6603 로또

www.acmicpc.net/problem/6603

6603번: 로또

 

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

public class BOJ_6603 {
    static int k;
    static int[] map;
    static boolean[] visited;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

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

        while (true) {
            String s = br.readLine();
            int k = (s.charAt(0)) - '0';

            if (k == 0) {
                break;
            }

            StringTokenizer st = new StringTokenizer(s, " ");

            int len = Integer.parseInt(st.nextToken());
            map = new int[len];
            visited = new boolean[len];
            arr = new int[6];

            for (int i = 0; i < map.length; i++) {
                map[i] = Integer.parseInt(st.nextToken());
            }

            backTracking(0);
            System.out.println(sb);
            sb.delete(0,sb.capacity());
        }

    }

    static void backTracking(int depth) {
        if (depth == 6) {
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < map.length; i++) {
            if (!visited[i]) {
                if (depth == 0 || arr[depth - 1] <= map[i]) {
                    visited[i] = true;
                    arr[depth] = map[i];
                    backTracking(depth + 1);
                    visited[i] = false;
                }
            }
        }

    }
}

N과 M과 유사한 백트래킹 문제다.

 

입력으로 주어진 정수 배열에서 6개를 뽑아 백트래킹을 돌리면 된다.

 

그러므로 depth가 6이 찍히면 StringBuilder에 넣어서 출력하고,

 

오름차순으로 정렬된 값만 선택해야 하므로 arr[depth - 1] <= map[i]인 경우만 포함하여 백트래킹을 돌린다.

 

    static void backTracking(int depth, int index) {
        if (depth == 6) {
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = index; i < map.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = map[i];
                backTracking(depth + 1, i);
                visited[i] = false;
            }
        }

    }

얘는 저기서 최적화 한거다. 한 10ms정도로 발라진다.

 

메소드의 파라미터를 1개 더 늘려서 반복문을 현재 index값부터 돌려서 오름차순을 만드는건데,

 

입력 배열이 정렬되어있을때만 가능하다. 이렇게 할 수도 있다고 알아두자~