BOJ(백준) 2309[일곱 난쟁이]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 2309번을 풀어보겠습니다. 이 문제는 주어진 9명의 난쟁이 중 합이 100이 되는 7명의 난쟁이를 찾는 문제입니다. 아래는 문제를 해결하기 위한 접근 방법과 정답 코드입니다.

 

1. 문제 설명

주어진 9명의 난쟁이 키 중에서 합이 100이 되는 7명의 난쟁이를 찾는 문제입니다.

문제 URL: https://www.acmicpc.net/problem/2309

 

2. 접근법

1. 입력받기: 9명의 난쟁이 키를 입력받아 배열에 저장합니다.

2. 재귀 함수 사용: 9명의 난쟁이 중 7명을 선택하여 그 합이 100이 되는지 확인합니다.

3. 결과 출력: 합이 100이 되는 7명의 난쟁이 키를 오름차순으로 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 난쟁이의 키를 담는 배열
arr = []
for _ in range(9):
    arr.append(int(input()))  # 9명의 난쟁이 키를 입력받아 배열에 저장

# 정답인 난쟁이의 키를 담을 임시 배열과 결과 배열
tmp = []  # 현재 선택된 난쟁이들의 키를 임시로 담아둘 배열
ans = []  # 최종적으로 선택된 7명의 난쟁이의 키를 담을 배열

def acc(idx, num):
    global ans     				# 전역 변수 ans를 사용하기 위해 선언
    global tmp
    if num == 7:  				# 7명의 난쟁이를 선택한 경우
        if sum(tmp) == 100:  	# 선택된 7명의 난쟁이 키의 합이 100인 경우
            ans = sorted(tmp)   # 정답을 전역 변수 ans에 저장 (정렬된 상태로)
        return  # 함수 종료

    # idx부터 시작하여 남은 난쟁이들을 선택
    for i in range(idx, len(arr)):  # 인덱스 변수 i 사용
        if arr[i] not in tmp:       # 현재 선택된 난쟁이들(tmp)에 포함되지 않은 경우
            tmp.append(arr[i])      # 해당 난쟁이의 키를 tmp에 추가
            acc(i + 1, num + 1)     # 다음 난쟁이를 선택하기 위해 재귀 호출 (인덱스를 i + 1로 증가)
            tmp.pop()               # 재귀 호출 이후 다시 되돌아와서 마지막에 추가한 난쟁이의 키를 제거

# 재귀 함수 호출 시작 (인덱스 0부터, 현재 선택된 난쟁이 수 0명)
acc(0, 0)

# 최종적으로 선택된 7명의 난쟁이 키를 출력
for i in ans:
    print(i)

 

4. 코드 설명

1) 입력받기

• sys.stdin.readline을 사용하여 9명의 난쟁이 키를 입력받습니다.

2) 장애물 데이터 입력

• 각 난쟁이의 키를 입력받아 배열 arr에 저장합니다.

3) 누적합 배열 초기화

• tmp 배열은 현재 선택된 난쟁이 키를 임시로 저장하고, ans 배열은 최종적으로 선택된 7명의 난쟁이 키를 저장합니다.

4) 재귀 함수 사용

• acc 함수는 재귀적으로 7명의 난쟁이를 선택하고, 이들의 키 합이 100이 되면 ans 배열에 저장합니다.

5) 결과 출력

• ans 배열의 값을 출력하여 선택된 난쟁이들의 키를 오름차순으로 출력합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_04_03_2309.py at main · pcy4196/coTest