[파이썬] 2309번 : 일곱 난쟁이

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

2309번: 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1 복사

20
7
23
19
10
15
25
8
13

예제 출력 1 복사

7
8
10
13
19
20
23

 

생각

9개중 7개를 선택을 해서 비교를 해야하는데 그 합이 100이어야 한다.

이런경우에 있어서 어떤 것을 선택해야할지 너무 애매하다는 생각이 들었다.

그래서 random모듈을 이용해서 해보자 라고 생각했다.

푼 코드이고 맞은 코드이다.

 

import sys
import random
heights=[int(sys.stdin.readline()) for _ in range(9)]
stack= []
while True:
    num = random.randint(0,8)
    stack.append(num)
    if len(set(stack))<7:
        continue
    elif len(set(stack))==7:
        stack=[heights[i] for i in set(stack)]
        if sum(stack)==100:
            break
        else:
            stack = []
print(*sorted(stack))

 

내가 풀었던 방식은 radom하게 해 진짜로 시간복잡도가 좀 복잡하다고 생각이 들었다.

또한 메모리적으로도 많이 사용한다고 느꼈다.

그래서 다른 풀이를 찾아보았다,

 

list = [int(input()) for i in range(9)]

total = sum(list)

for i in range(9):
    for j in range(i+1,9):
        if 100 == total - (list[i] + list[j]): 
            num1,num2=list[i],list[j]

            list.remove(num1)
            list.remove(num2)
            list.sort() # 오름차순 정리

            for i in range(len(list)):
               print(list[i])
            break

    if len(list)<9:
        break

맨처음에 다 더한결과를 가지고하는데 9개에서 7개로 하면 되니까 2개를 빼는데에 있어서 이중 for문을 사용하였고

 

만약 합이 100이 된다면 원래의 llist에서 2개를 제거해주면 되는 것이었다.

 

내가 너무 어렵게 생각했나보다..