greentea31's Note

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

풀이 과정

9명중에 진짜 난쟁이를 7명 찾아야 하고 7명의 키의 합이 100이라 한다.

-> 모든 난쟁이의 키의 합을 구하고 9명중에 2명의 난쟁이의 키의 합을 뺐을 때 100이 나오면 그 2명은 진짜 난쟁이가 아니다

루프 2번 돌면서 9명중에 2명의 난쟁이를 고르는 수인 36번 돌다 보면 가짜 난쟁이 2명이 걸러진다 브루트 포스 방법으로 2명 뺐을 때 키의 합이 100이 나올때까지 다 찾아보면 된다.

키의 합을 구하는 연산 O(N), 가짜 난쟁이 2명을 찾는 연산 O(N^2)으로 총 O(N^3)의 시간복잡도를 갖고, N이 9이므로 그냥 다 해봐도 시간제한 내로 문제를 해결하는데 문제가 없다.

소스 코드

import sys
height = []

for i in range(9):
    height.append(int(sys.stdin.readline()))

height.sort()

sumHeight = sum(height)

fake1 = 0
fake2 = 0

for i in range(8):
    for j in range(i+1, 9):
        if sumHeight - height[i] - height[j] == 100:
            fake1 = i
            fake2 = j

for i in range(9):
    if i != fake1 and i != fake2:
        print(height[i])