각 조합을 확인하기 위해 조합의 키를 합산하고, 합계가 100인지 확인하는 과정은 각 조합에 대해 상수 시간 O(N)이 소요된다.
따라서 조합을 확인하는 시간은 O(7)이다.
문제 조건 분석 과정
9개의 난쟁이 키를 입력받아 배열에 저장한다.
비트마스크를 통해 9명의 난쟁이 중 7명을 선택하는 모든 조합을 생성한다.
각 조합에 대해 선택된 7명의 키를 합산한다.
키의 합이 100이 되면, 해당 조합을 선택하여 결과를 출력한다.
찾은 조합을 오름차순으로 정렬하고, 각 난쟁이의 키를 출력한다.
전체코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 9명의 난쟁이의 키를 저장할 배열
int[] heights = new int[9];
// 9명의 난쟁이의 키를 입력받아 배열에 저장
for (int i = 0; i < 9; i++) {
heights[i] = Integer.parseInt(br.readLine().trim());
}
// 7명의 난쟁이를 찾는 메서드를 호출
findSevenDwarfs(heights);
}
// 7명의 난쟁이를 찾는 메서드
private static void findSevenDwarfs(int[] heights) {
int n = heights.length; // 난쟁이의 총 수 (9명)
int targetSum = 100; // 찾고자 하는 키의 총합
int[] combination = new int[7]; // 7명의 난쟁이를 저장할 배열
// 9명 중 7명을 선택하기 위한 모든 조합을 생성한다.
for (int i = 0; i < (1 << n); i++) {
// 현재 조합이 7명의 난쟁이로 구성되었는지 확인한다.
if (Integer.bitCount(i) == 7) {
int sum = 0; // 현재 조합의 키 합계
int index = 0; // 조합 배열의 인덱스
// 현재 조합에 포함된 난쟁이의 키를 계산한다.
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
sum += heights[j];
combination[index++] = heights[j];
}
}
// 키의 합이 100이라면, 정렬 후 출력하고 메서드를 종료한다.
if (sum == targetSum) {
Arrays.sort(combination);
for (int height : combination) {
System.out.println(height);
}
return; // 메서드를 종료하여 더 이상의 조합을 찾지 않도록 한다.
}
}
}
}
}
