일곱 난쟁이

제출코드

시간초과

모범답안

package baekjoon;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] dwarves = new int[9];
        int totalHeight = 0;

        for (int i = 0; i < 9; i++) {
            dwarves[i] = Integer.parseInt(br.readLine());
            totalHeight += dwarves[i];
        }

        Arrays.sort(dwarves);  // 난쟁이 키를 오름차순으로 정렬

        // 두 난쟁이를 찾는 과정
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                // 두 난쟁이를 제외한 키의 합이 100이 되는 경우
                if (totalHeight - dwarves[i] - dwarves[j] == 100) {
                    // 해당 난쟁이를 제외하고 출력
                    for (int k = 0; k < 9; k++) {
                        if (k == i || k == j) {
                            continue; // 제외되는 난쟁이는 출력하지 않음
                        }
                        System.out.println(dwarves[k]);
                    }
                    return; // 일곱 난쟁이를 찾았으므로 프로그램 종료
                }
            }
        }
    }
}

• 오름차순 후 출력하라고 했다고 해서 값을 찾은 후에 정렬을 할 필요는 전혀 없다.
• 신기하게도 7개의 요소들을 모두 더해서 찾는게 아니라 2중 반복문을 통해
  totalHeight - 난쟁이1의 키 - 난쟁이2의 키 = 100 이라는 수식으로 구했다.
• 일일히 더해서 100이 되는 경우의 수를 찾을 수는 있지만, 더 복잡해진다.

import java.util.*;

public class Main {
    static int[] dwarves = new int[9];
    static int[] selected = new int[7];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            dwarves[i] = scanner.nextInt();
        }
        findDwarves(0, 0, 0);
    }

    public static void findDwarves(int start, int depth, int sum) {
        if (depth == 7) {
            if (sum == 100) {
                for (int i = 0; i < 7; i++) {
                    System.out.println(selected[i]);
                }
                System.exit(0);
            }
            return;
        }

        for (int i = start; i < 9; i++) {
            selected[depth] = dwarves[i];
            findDwarves(i + 1, depth + 1, sum + dwarves[i]);
        }
    }
}

• 배열의 9개의 요소 중, 가능한 모든 7개의 조합을 만드는 것을 구현하기 위해 i < 9, j < 9 를 설정하였다.

이 코드에서 i < 9와 j < 9로 설정한 이유는 난쟁이가 총 아홉 명이기 때문이다.

반복문에 사용된 for (int i = 0; i < 9; i++)는 첫 번째 난쟁이부터 시작하여 마지막 난쟁이까지 순회한다.
for (int j = i + 1; j < 9; j++)는 i번째 난쟁이 다음 위치에서 시작하여 배열의 끝까지 순회한다. 이렇게 설정함으로써, i와 j는 각각 서로 다른 두 난쟁이를 가리키게 되며, 어떠한 난쟁이 조합도 놓치지 않고 검사할 수 있다.

이중 반복문을 사용하여 모든 가능한 난쟁이 쌍 (i, j)를 검사하고, 이들 두 난쟁이의 키의 합을 전체 키의 합에서 빼서 100이 되는 경우를 찾는다.
이 조건을 만족하는 난쟁이 쌍을 찾으면, 이 두 난쟁이를 제외한 나머지 난쟁이들의 키를 출력한다.

• n중반복문 예시
  3중 반복문을 사용하여 배열 내의 모든 가능한 세 수의 조합의 합을 찾고, 그 중에서 가장 큰 합을 구하는 로직을 구현해보자. [1,2,3,4,5]가 주어졌을 때, 모든 세 수의 조합의 합을 구하고 가장 큰 값을 찾는다.

public class Main {
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};  // 입력 배열
        int maxSum = Integer.MIN_VALUE;  // 최대 합을 저장할 변수, 최소값으로 초기화

        // 모든 세 수 조합의 합을 구하기 위한 3중 반복문
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                for (int k = j + 1; k < numbers.length; k++) {
                    // 현재 조합의 합을 계산
                    int sum = numbers[i] + numbers[j] + numbers[k];
                    // 현재 조합의 합이 이전의 최대 합보다 큰 경우, 최대 합을 업데이트
                    if (sum > maxSum) {
                        maxSum = sum;
                    }
                }
            }
        }

        // 가장 큰 합 출력
        System.out.println("가장 큰 합: " + maxSum);
    }
}

배운점

1. 문제를 풀 때 수동적으로 풀 필요가 없다.

   • 정렬 후 출력하라고 했다고 해서, 정렬을 맨 마지막에 할 필요는 전혀 없다.
   • 9개의 수 중 7개의 합이 100인 수를 구하라고 했다고 해서, 7개를 더할 필요가 전혀 없다. 9개에서 2개를 빼면 문제는 매우 간단해진다.

2. 팁) n중반복문을 통해 모든 경우의 수를 탐색하고자 할 때, 반복문의 두번째 요소는 배열의 전체길이 로 고정하면 된다.

3. Integer.MIN_VALUE는 자바에서 int 타입의 최소값을 나타내는 상수다.
   int 타입은 32비트 정수형으로, Integer.MIN_VALUE는 -2^31, 즉 -2,147,483,648의 값을 갖는다.