일곱 난쟁이

[hsskey]

일곱 난쟁이

아홉 명의 난쟁이 중 진짜 일곱 난쟁이를 찾는 문제입니다. 일곱 난쟁이의 모자에 쓰인 숫자의 합이 100이 되어야 합니다.

📝 제약조건

• 입력되는 수는 1 이상 99 이하의 자연수
• 모든 숫자는 서로 다름
• 항상 답이 유일한 경우만 입력으로 주어짐
• 7명의 난쟁이 모자 숫자의 합이 100이어야 함

💡 예시

• Input:

7
8
10
13
15
19
20
23
25

• Output:

7
8
10
13
19
20
23

문제 해결 과정

Step 1: 문제 이해하기

작은 예시로 직접 풀어보기:

• 입력: [3, 4, 5, 6, 7, 8, 9, 10, 11]
• 이 중 7개를 골라 합이 100이 되는 경우를 찾아야 함
• 모든 조합을 시도해볼 수 있음 (완전탐색)

Step 2: 접근 방법

• 직관적으로 생각하기

  1. 9명 중 7명을 선택하는 모든 조합을 확인
  2. 각 조합의 합이 100인 경우를 찾음
  3. 답이 유일하므로 찾으면 바로 종료 가능

• 알고리즘 표 작성

start = 0, curr = [] (초기 설정)
↓
현재 배열 길이가 7이고 합이 100인지 확인
↓
맞다면 -> 정답 배열에 저장하고 종료
아니라면 -> 다음 수 선택
↓
start부터 9까지 순회하며:
  - 현재 수를 curr에 추가
  - 다음 수로 재귀 호출
  - 현재 수를 curr에서 제거

Step 3: 코드 설계

1. 입력값 처리 및 숫자 배열 생성
2. 백트래킹 함수 구현:
   • 현재까지 선택된 수들을 담은 배열 관리
   • 7개가 선택되고 합이 100이면 정답으로 저장
   • 아직 7개가 안 되었다면 다음 수 선택 시도
3. 정답 출력 처리

Step 4: 코드 구현

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const arr = input.map(Number)
const ans = []

function backtrack(start, curr) {
    if(curr.length === 7 && curr.reduce((acc, item) => acc + item, 0) === 100) {
        ans.push(...curr)
        return
    }

    for(let i = start; i < arr.length; i++) {
        curr.push(arr[i])
        backtrack(i + 1, curr)
        curr.pop()
    }
}

backtrack(0, [])
console.log(ans.join('\n'))