B3040. 백설 공주와 일곱 난쟁이

문제

제출 코드

• 사용 알고리즘 : 조합
• 출력 결과가 두번 찍혀서, 뭔가 조합이 두번 만들어지는거 같아 일단 예외처리 해주고 제출
• 나중에 순조부 공부 다시하고 코드를 보니까 조합 코드를 잘못짬
• 수정 전

  package bronze;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B3040_SnowWhite {
  	static boolean finish;
  	static int[] dwarf;
  	static boolean[] selected = new boolean[9];
  
  	static void selectHat(int n, int now, int sum) {
  		if(n==7) {
  			if(sum == 100) {
  				for(int i=0; i<9; i++) {
  					if(selected[i]) System.out.println(dwarf[i]);
  				}
  				finish = true;
  			}
  			return;
  		}
  
  		for(int i=now; i<9; i++) {
  			if(finish) return;		// 이 코드가 없으면 결과가 두번 찍힘 왜지
  			selected[i] = true;
  			selectHat(n+1, i+1, sum+dwarf[i]);
  			selected[i] = false;
  			selectHat(n, i+1, sum);
  		}
  	}
  
  	public static void main(String[] args) throws NumberFormatException, IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
  		dwarf = new int[9];
  		for(int i=0; i<9; i++) {
  			dwarf[i] = Integer.parseInt(br.readLine());
  		}
  
  		selectHat(0, 0, 0);
  	}
  
  }
  

• 수정 후

  package bronze;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B3040_SnowWhite {
  	static boolean finish;
  	static int[] dwarf;
  	static int[] selected = new int[7];
  
  	/* 조합을 통해 7명의 난쟁이를 선택하는 메소드
  	 * - n : 지금까지 선택된 난쟁이 수
  	 * - now : 남은 난쟁이들 중 가장 앞 인덱스
  	 * - sum : 선택된 난쟁이 모자 숫자 합
  	 */
  	static void selectDwarf(int n, int now, int sum) {
  		if(n==7) {
  			if(sum == 100) {
  				for(int i=0; i<7; i++) {
  					System.out.println(dwarf[selected[i]]);
  				}
  			}
  			return;
  		}
  
  		for(int i=now; i<9; i++) {
  			selected[n] = i;
  			selectDwarf(n+1, i+1, sum+dwarf[i]);
  		}
  	}
  
  	public static void main(String[] args) throws NumberFormatException, IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
  		dwarf = new int[9];
  		for(int i=0; i<9; i++) {
  			dwarf[i] = Integer.parseInt(br.readLine());
  		}
  
  		selectDwarf(0, 0, 0);
  	}
  
  }