[백준] 일곱 난쟁이

hyun·2022년 5월 17일
0

알고리즘 문제

목록 보기
9/10
post-thumbnail

https://www.acmicpc.net/problem/2309

브론즈 2티어의 쉬운 문제였으나, 나의 사고력 부족과 게으름이 여실히 드러난 문제였기 때문에 반성의 의미로 포스팅한다.

문제 이해

9명의 난쟁이의 키가 주어졌을 때, 9명의 난쟁이 중 진짜 7명의 난쟁이를 찾아야 한다. 찾는 근거는 7명의 키의 합이 100이라는 것이다. 조건을 만족한다면 아무 조합의 7명의 난쟁이를 오름차순으로 출력하면 된다.

문제 접근

제일 처음 떠올랐던 풀이법은 가장 직관적이고 쉬운 방법이었다. 9명의 난쟁이에 대해 가능한 모든 7명 구성을 나열하고, 모든 조합에 대해 합을 구해 100이면 그 조합을 출력하는 방법이다.

실패한 풀이 코드

from itertools import combinations
data = [int(input()) for i in range(9)]

candidates = list(map(list,combinations(data, 7)))
for c in candidates:
    if sum(c) == 100:
        c.sort()
        for i in range(len(c)):
            print(c[i], end="\n")

너무 무식하고 더러운 코드가 탄생했다. 심지어 테스트케이스는 맞게 나왔으나, 문제를 통과하지도 못했다.

다른 접근

7명의 난쟁이의 키의 합이 100이라는 것은, 9명 중에서 2명을 뺐을 때 100이 된다는 것과 같은 말이다.

성공한 풀이 코드

data = [int(input()) for i in range(9)]
total = sum(data)

for i in range(9):
    for j in range(i+1, 9):
        if total - (data[i] + data[j]) == 100:
            a, b = data[i], data[j]
            data.remove(a)
            data.remove(b)
            data.sort()
            for i in range(len(data)):
               print(data[i])
            break
    if len(data) != 9:
        break

이중 for문을 돌며 제외해 볼 2명을 선별하고, 그 둘을 제외했을 때의 키의 총합이 100이라면 데이터에서 제거한 후 출력한다. 조건을 만족하는 아무 조합이나 한 번만 출력하면 되니까 출력을 한 후에는 바로 break를 걸어준다. 그리고 한 명이라도 제거가 되었다면 출력을 한 것이므로, 9명이 아니라면 가장 바깥의 for문을 빠져나온다.

회고

너무 직관적으로만 생각하는 경향이 있다. combinations을 쓰기 전에 이게 맞나 생각했어야 했다. 너무 쉽게 가려고 하지 말자.

profile
프론트엔드를 공부하고 있습니다.

0개의 댓글