BOJ 2309_일곱 난쟁이

 

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

 

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1 

20
7
23
19
10
15
25
8
13

예제 출력 1

7
8
10
13
19
20
23

 

 

배열 사이즈를 9로 고정해 놓고 7개 조합을 찾아서 합이 100이면 출력하면 되는데

그걸 못해서 여기다가 올리고 있음 ;; 퇴화 ㄹㅈㄷ 

 

import java.util.Arrays;

 

public class BOJ_2309 {

// 일곱 난쟁이

  static int[] dwarfs = new int[9];

  static int[] result = new int[7];

  static java.util.ArrayList<Integer> answer = new java.util.ArrayList<>();

 

  public static void main(String[] args) {

    java.util.Scanner sc = new java.util.Scanner(System.in);

    for(int i = 0; i<dwarfs.length; i++) {

      dwarfs[i] = sc.nextInt();

    }

 

    findDwarfs(0);

  for(int i : result) System.out.println(i);

 

}

// 일곱 명 모든 경우의 수를 찾아 합이 100인지를 확인한다.

 

  static void findDwarfs(int index) { // DFS

    if(index >= dwarfs.length) return;

    if(answer.size() == 7) { // 검증

      int[] semi = new int[7];

      for(int i = 0; i<7; i++) {

        semi[i] = answer.get(i);

      }

      Arrays.sort(semi);

      System.out.println(Arrays.toString(semi)); // 조합 확인하기

 

      int sum = 0;

      for(int i : answer) {

        sum += i;

       }

       if(sum == 100) { // pass 조건

         for(int i = 0; i<result.length; i++) {

            result[i] = answer.get(i);

         }

         Arrays.sort(result);

         System.out.println(Arrays.toString(result));

       }

       else return;

      } // second if

    else if(answer.size()>7) return;

 

  // answer 배열에 넣지 말자

    findDwarfs(index+1);

 

  // answer 배열에 넣자

    answer.add(dwarfs[index]);

    findDwarfs(index+1);

    answer.remove(answer.indexOf(dwarfs[index]));

 

    }

 

}

 

들여쓰기 이상하다 

import java.util.Arrays;

public class BOJ_2309 {
	// 일곱 난쟁이
	static int[] dwarfs = new int[9];
	static int[] result = new int[7];
	static java.util.ArrayList<Integer> answer = new java.util.ArrayList<>();
	
	public static void main(String[] args) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
		for(int i = 0; i<dwarfs.length; i++) {
			dwarfs[i] = sc.nextInt();
		}
		
		findDwarfs(0);
		for(int i : result) System.out.println(i);
		
	}
	// 일곱 명 모든 경우의 수를 찾아 합이 100인지를 확인한다.
	
	static void findDwarfs(int index) { // DFS
		if(index >= dwarfs.length) return;
		if(answer.size() == 7) { // 검증
			int[] semi = new int[7];
			for(int i = 0; i<7; i++) {
				semi[i] = answer.get(i);
			}
			Arrays.sort(semi);
			System.out.println(Arrays.toString(semi)); // 조합 확인하기
			
			int sum = 0;
			for(int i : answer) {
				sum += i;
			}
			if(sum == 100) { // pass 조건
				for(int i = 0; i<result.length; i++) {
					result[i] = answer.get(i);
				}
				Arrays.sort(result);
				System.out.println(Arrays.toString(result));
			}
			else return;
		} // second if
		else if(answer.size()>7) return;
		
		// answer 배열에 넣지 말자 
		findDwarfs(index+1);
		
		// answer 배열에 넣자
		answer.add(dwarfs[index]);
		findDwarfs(index+1);
		answer.remove(answer.indexOf(dwarfs[index]));
		
	}

}

이렇게 보는 게 나을지도

 

아무튼 어차피 완탐이라 DFS로 짜려고 했는데

뭐가 잘 안 됐다 마지막 난쟁이가 무조건 안 들어감 ; 왜지? 

조건문 인덱스 문제 같은데 머리가 안 굴러간다 뭐가 문제지

23

19

10

15

25

8

13

20

7

[8, 10, 13, 15, 19, 20, 25]

[8, 10, 13, 15, 20, 23, 25]

[8, 13, 15, 19, 20, 23, 25]

[8, 10, 13, 19, 20, 23, 25]

[8, 10, 13, 15, 19, 20, 23]

[10, 13, 15, 19, 20, 23, 25]

[8, 10, 15, 19, 20, 23, 25]

[8, 10, 13, 15, 19, 23, 25]

0

0

0

0

0

0

0

TC 넣고 돌리면 result는 이렇게 나온다. 경우의 수도 충분하지 않고 ... 걍 졸라 당황스러움 ㅋㅋ

참고로 마지막 인덱스에 답안이 포함되지 않도록 돌리면

7

8

10

23

20

19

13

25

15

[8, 10, 13, 19, 20, 23, 25]

[7, 10, 13, 19, 20, 23, 25]

[7, 8, 13, 19, 20, 23, 25]

[7, 8, 10, 13, 19, 20, 25]

[7, 8, 10, 13, 19, 23, 25]

[7, 8, 10, 13, 20, 23, 25]

[7, 8, 10, 19, 20, 23, 25]

[7, 8, 10, 13, 19, 20, 23]

[7, 8, 10, 13, 19, 20, 23]

[7, 8, 10, 13, 19, 20, 23]

[7, 8, 10, 13, 19, 20, 23]

7

8

10

13

19

20

23

결과는 잘 출력된다. 인덱스 문제가 맞음

왜 마지막 난쟁이까지 검토하지 못하는 걸까 흐핳

 

 

내가 진짜 너무 멍청하게 느껴져서

간단하게 아래 코드를 짜 봤다. 

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;

public class BOJ_2309 {
	// 세 개 중에 두 개를 뽑는 경우의 수
	static int[] arr = new int[3];
	static Stack<Integer> pick = new Stack<>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int i = 0; i<3; i++) {
			arr[i] = sc.nextInt(); // 숫자 세 개 입력하기
		}
		pick2(0);
	}
	
	public static void pick2(int index) {
		if(index >= 3) {
			// 끝까지 다 돌았다
			if(pick.size() == 2) {
				System.out.println(Arrays.toString(pick.toArray()));
			}
			
			return;
		} // index > 3 
		
		// arr[index]를 답안에 포함하기
		pick.add(arr[index]);
		pick2(index+1);
		
		// arr[index]를 답안에서 제외하기
		pick.pop();
		pick2(index+1);
	}
}

1

2

3

[1, 2]

[1, 3]

[2, 3]

기대했던 대로 아주 잘 나온다.

이 구조를 그대로 덮어씌워 보겠음

 

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class BOJ_2309 {
	static int[] arr = new int[9];
	static int[] result = new int[7];
	static Stack<Integer> pick = new Stack<>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int i = 0; i<arr.length; i++) {
			arr[i] = sc.nextInt(); // 
		}
		pick7(0);
		
		Arrays.sort(result);
		for(int i : result) System.out.println(i);
			
	}
	
	public static void pick7(int index) {
		if(index >= arr.length) {
			// 끝까지 다 돌았다
			if(pick.size() == 7) {
				// System.out.println(Arrays.toString(pick.toArray())); // 조합 확인하기
				int sum = 0;
				for(int i : pick) {
					sum += i;
				}
				if(sum == 100) {
					for(int i = 0; i<result.length; i++) {
						result[i] = (int) pick.toArray()[i];
					}
					// 원본 stack의 요소와 순서를 건드리지 않도록 주의한다. 남은 DFS 시행이 있기 때문임 
				}
			}
			return;
		} 
		
		// arr[index]를 답안에 포함하기
		pick.add(arr[index]);
		pick7(index+1);
		
		// arr[index]를 답안에서 제외하기
		pick.pop();
		pick7(index+1);
	}
}

풀었다