공부 168일차: 백준 6603번 로또 자바 java

6603 로또

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

6603번: 로또

 

 

 

---

백준 6603번 문제 로또

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/297

공부 157일차: 백준 15655번 N과 M (6) 자바 java

참고하면 좋은 문제

 

 

문제가 길어보이지만, 결국 아래 예제처럼

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

한줄에 k k(0) k(1) ... k(k-1) 가 주어지고

주어진 k(0)...k(k-1)을 집합 s라 부르며, 이 집합에서 길이 6의 숫자 조합을 만들어내면 된다

 

총 6개의 숫자를 뽑아낸다는 것은 DFS에서 깊이 6개까지 간다는 의미이며,

오름차순으로 뽑아내야 한다

 

오름차순을 주는 방법은

1) 반복문을 한 번 더 돌린다

2) start 변수를 둔다

 

내가 적용한 방법은 1번

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int k;
    static int[] arr, nums;
    static boolean[] visited;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    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) {    // 0 입력되면 반복문 중지
                break;
            }
            arr = new int[k];
            nums = new int[k];
            visited = new boolean[k];
            
            for(int i = 0; i < k; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }
            
            DFS(0);
            bw.newLine();    // 테스트 케이스마다 분리
        }
        
        bw.flush();
        bw.close();
    }
    
    static void DFS(int depth) throws IOException{
        if(depth == 6) {    // 로또는 총 6개 숫자
            // arr에는 0 0도 들어가므로 6개 숫자만 꺼낼 수 있도록 제한을 둔다        
            for(int i = 0; i < 6; i++) {    
                bw.write(arr[i] + " ");
            }
            bw.newLine();
            return;
        }
        
        for(int i = 0; i < k; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[depth] = nums[i];
                DFS(depth+1);
                for(int j = i+1; j < k; j++) {    // 오름차순 나열을 위함(매개변수에 start 두는 방법도 있음)
                    visited[j] = false;
                }                    
            }
        }
    }
 
}

 

 

 

---

N과 M 문제들을 풀었던 게 매우 큰 도움이 되고 있다!