[Python] 백준 2309 일곱 난쟁이

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

2309번: 일곱 난쟁이

문제 해결

리스트 안에 두 개의 원소를 빼는 방법을 선택

뺄 두 개원 원소 인덱스중 작은 인덱스를 start, 큰 인덱스를 end로 잡고 하려고 함.

알고 있는 지식이 전체 수의 합이므로 리스트를 sort 시킨 후 start, end 포인트 이동이 편할 것 같다.

시간 복잡도면에서 더 효율적인 것이 있을 것 같지가 않았다. (Brute force algorithm)

 

CODE

import sys
input = sys.stdin.readline
A = [int(input()) for _ in range(9)]
total = sum(A)
A.sort()
start = 0
end = 8
while start < end:
    ans = total - A[start] - A[end]
    if ans>100:
        start +=1
    elif ans < 100:
        end -=1
    else:
        A.remove(A[start])
        A.remove(A[end-1]) # A[start]를 제거해서 start 이후 인덱스는 왼쪽으로 한칸씩 밀려짐. 따라서 end-1
        break
for i in range(7):
    print(A[i])