[BOJ/Java] 3040. 백설 공주와 일곱 난쟁이

[BOJ/Java] 3040. 백설 공주와 일곱 난쟁이

3040번: 백설 공주와 일곱 난쟁이

---

문제 해석

이 문제는 9명의 난쟁이 중 진짜 일곱 난쟁이를 찾아내는 문제로, 진짜 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 정확히 100이 되어야 한다. 우리는 9명 중에서 7명을 선택해 그 합이 100이 되는 조합을 찾아내야 한다.

풀이 과정

제출된 Java 코드는 조합을 사용하여 문제를 해결한다. 9명의 난쟁이 중 7명을 선택하는 모든 조합을 생성하고, 선택된 난쟁이들의 숫자 합이 100이 되는 조합을 찾는다.

 

• 데이터 입력: BufferedReader를 통해 난쟁이의 숫자를 입력받아 배열에 저장한다.
• 조합 생성 (sol 메소드): 조합을 재귀적으로 생성하며, 선택된 7명의 난쟁이의 합이 100일 경우 결과를 StringBuilder에 저장한다.

코드

package edu.ssafy.im.BOJ.Bronze.B2.No3040;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	private static final int SIZE = 9; // 전체 난쟁이 수
	int[] arr = new int[SIZE]; // 난쟁이 모자의 숫자를 저장할 배열
	int[] sel = new int[7]; // 선택된 일곱 난쟁이를 저장할 배열
	StringBuilder sb = new StringBuilder(); // 결과를 저장할 StringBuilder

	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().io();
	}

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < SIZE; i++) {
			arr[i] = Integer.parseInt(br.readLine()); // 입력받은 난쟁이 숫자 저장
		}
		sol(0, 0); // 조합 생성 시작
		bw.write(sb.toString()); // 결과 출력
		bw.flush();
		bw.close();
	}

	private void sol(int i, int k) {
		if (sb.length() != 0) { // 이미 결과가 찾아진 경우
			return;
		}

		if (k == sel.length) { // 일곱 난쟁이가 선택된 경우
			int sum = 0;
			for (int j = 0; j < sel.length; j++) {
				sum += sel[j]; // 선택된 난쟁이들의 숫자 합 계산
			}
			if (sum == 100) { // 합이 100인 경우
				for (int j = 0; j < sel.length; j++) {
					sb.append(sel[j]).append("\n"); // 결과에 추가
				}
			}
			return;
		}
		
		for (int j = i; j < SIZE; j++) {
			sel[k] = arr[j]; // 난쟁이 선택
			sol(j+1, k+1); // 다음 난쟁이 선택을 위해 재귀 호출
		}
	}
}

시간 복잡도 분석

이 코드의 시간 복잡도는 조합을 생성하는데 드는 비용으로, C(9,7)=36 경우의 수를 고려해야 하므로 O(1)로 볼 수 있다. 실제 연산은 매우 제한적이다.

느낀점

이 문제를 통해 조합을 사용하여 특정 조건을 만족하는 해결책을 찾는 방법을 연습할 수 있었다. 문제의 규모가 작기 때문에 직접적인 조합 접근이 가능했으며, 이러한 접근은 비슷한 유형의 다양한 문제에 적용될 수 있다.