[백준] 2309번_일곱난쟁이

문제 링크 : https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

import sys
dwarf = []
for _ in range(9):
    dwarf.append(int(input()))
for i in range(8):
    for j in range(i+1,9):
        sum_ = 0
        for d in range(len(dwarf)):
            if d!=i and d!=j:
                sum_ += dwarf[d]
        if sum_ == 100:
            dwarf[i] = dwarf[j] = 0
            dwarf = sorted(dwarf)
            for d in dwarf:
                if d!=0:
                    print(d)
            sys.exit()

위의 코드는 시간복잡도 O(N^3)이다.

새로운 i,j가 나올 때마다 그 i,j를 제외한 나머지 인덱스에 대한 합을 구하는 대신,

처음에 아홉 난쟁이들의 키의 합을 구한 후, 빼주는 방식으로 한다면 O(N^2)을 가질 수 있다.

dwarf = []
tall = 0
for i in range(9):
    dwarf.append(int(input()))
    tall += dwarf[i]
dwarf = sorted(dwarf)
for i in range(8):
    for j in range(i+1,9):
        if (tall-dwarf[i]-dwarf[j] == 100):
            for t in range(len(dwarf)):
                if t!=i and t!=j:
                    print(dwarf[t])
            sys.exit()