[백준] 6603번 로또 JAVA (자바) 풀이

문제 6603번 (백트래킹)

 

 :  {1, 2, ..., 49}에서 6개 택

 

 :  k개(k>6) 골라 집합 S 만들어 6개의 조합 만들기

 

 

 [입력]

 :  각 줄의 첫 번째 수는 k (6 < k < 13), 다음 k개 수는 집합 S에 포함되는 수

    (입력 마지막 줄 = 0) 

 [출력]

 :  각 테스트 케이스마다 경우의 수 출력 (사전 순 / 중복 금지)

 

 :  각 테스트 케이스 사이에는 빈 줄 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹

 

 문제 조건 1) 숫자 중복금지 
 문제 조건 2) 수열 원소 오름차순 

 

 종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false

 

 N과 M(2) 문제 응용버전이다
 마찬가지로 boolean이 필요없다

 현재 숫자보다 무조건 다음 인덱스의 숫자가 커져야 하기 때문에 

 굳이 방문기록을 체크해가며 숫자를 추가하기보다

 현재 숫자 + 1을 백트래킹에 넣어서 돌리고 for문 시작지점을 조정하면 된다

 

※ 개행 중요 ※
 

• 하나의 테스트 케이스에서 백트래킹에서 이미 '\n'으로 개행 
   = 다음줄로 넘어가 이어쓰기
• 메인메서 메서드에서  테스트 케이스 끝날때마다 (최종 백트래킹까지 모두 거쳤을 때) 한 번 더  '\n' 개행
   =  다음줄로 넘어가 이어쓰기 X 2 = 한 줄 빈 줄

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int arr[],k,result[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        while(true) {
        st=new StringTokenizer(br.readLine());
        k=Integer.parseInt(st.nextToken());
        arr=new int[k];
        result = new int[6];
            
        if(k==0)
            break;
    
        for(int i =0; i<k; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        back(0, 0);
        sb.append('\n'); 
        }
        
        System.out.print(sb);
    }
    
    public static void back(int depth, int next){
        if(depth==6){
            for(int i:result){
                sb.append(i).append(" ");
            }
            sb.append('\n');
            return;
        }
        
        for(int i=next; i<k; i++){
            result[depth]=arr[i];
            back(depth+1, i+1);
        }
    }
}

 

 

 [해설]
     

 :  static int arr[],k,result[];
    static StringBuilder sb = new StringBuilder();
   

 :  while(true) {  각 테스트 케이스 반복
        st=new StringTokenizer(br.readLine());  
        k=Integer.parseInt(st.nextToken());
        arr=new int[k];  입력받은 S집합
        result = new int[6];  내가 조합한 6가지 로또번호
            
        if(k==0)  0 입력 받음 종료
            break;
    
        for(int i =0; i<k; i++){   S집합 입력받기
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        back(0, 0);  백트래킹 시작
        sb.append('\n');  테스트 케이스 끝날 때마다 한 줄 더 띄기
        }
        
        System.out.print(sb);  while문 끝나고 출력
    }

    
 :  public static void back(int depth, int next){
        if(depth==6){  6개 뽑고 끝
            for(int i:result){
                sb.append(i).append(" ");
            }
            sb.append('\n');  개행
            return;
        }
        
        for(int i=next; i<k; i++){
            result[depth]=arr[i];  현재 result 인덱스에 arr에서 숫자 뽑아 차례로 넣기
            back(depth+1, i+1);  다음 백트래킹 인덱스, 다음 result 인덱스에 들어갈 숫자 arr 인덱스
        }
   }
  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

6603번: 로또

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *