브루트 포스 - 백준 2309 [Python]

브루트 포스 : 모든 방법을 한번씩 시도해보는 알고리즘 O(방법의 개수 * 시도하는 복잡도)

1. 문제의 가능한 경우의 수를 계산해본다.
2. 가능한 모든 방법을 다 만들어본다. > 그냥 다 해보는 방법, for문, 순열, 재귀 호출 사용, 비트마스크 사용
3. 각각의 방법을 이용해 답을 구해본다.

Problem)

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

2309번: 일곱 난쟁이

 

Solution)

• 난쟁이의 키는 변하지 않는다는 조건을 이용한다.
• 모든 키의 합 sum을 구한다.
• 7난장이의 키에 포함되지 않는 것을 i,j로 설정하여 sum에서 뺀다.

위 방법으로 접근한다면 O(N^2)으로 문제를 해결할 수 있다.

 

Answer)

import sys
n = 9
a = [int(input()) for _ in range(n)]
a.sort()
total = sum(a)
for i in range(0, n):
    for j in range(i+1, n):
        if total - a[i] - a[j] == 100:
            for k in range(0, n):
                if i == k or j == k:
                    continue
                print(a[k])
            sys.exit(0)