우주의 IT 소행성

1. 9명의 난쟁이 중에서 7명을 찾는 방법

2. 9명의 난쟁이 중에서 2명을 찾는 방법

브루트포스로 문제를 해결할 수 있고,

itertools의 combinations을 사용해 문제를 해결할 수 있다.

#  combinations를 사용해 문제를 해결한 코드
from itertools import combinations
data = [int(input()) for _ in range(9)]

for i in combinations(data, 7):
    if sum(i) == 100:
        result = list(i)
        break

result.sort()
for i in result:
    print(i)

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

O(n^2)의 코드로, 두 코드간 실행에는 큰 차이가 없음을 확인할 수 있었다.

MAX = 1000000
check = [0] * (MAX + 1)
check[0] = check[1] = True
prime = []

for i in range(2, MAX + 1):
    if not check[i]:
        prime.append(i)
        j = i + i
        while j <= MAX:
            check[j] = True
            j += i
prime = prime[1:]

while True:
    n = int(input())
    if n == 0:
        break
    for p in prime:
        if (n - p) < 0:
            print("Goldbach's conjecture is wrong.")
            break
        elif not check[n - p]:
            print(f'{n} = {p} + {n - p}')
            break

에라토스테네스의 체을 이용해 MAX인 1000000 까지의 소수의 배수들을 모두 걸러주고 PRIME 리스트를 만들어준다.

A + B = N ( A, B, C 는 모두 소수) 라는 골드바흐의 추측 공식을 기억해보자.

A가 P라고 할때 P + B = N 이고

B = N - P가 된다.

따라서 prime을 하나씩 꺼내주면서 n-p를 찾아주면 된다.

n - p가 음수일 경우 goldbach's conjecture is wrong을 출력해준다.

문제의 규칙성을 계산해보고 풀면 DP문제라는 것을 알아 챌 수 있다.

1 - 1

2 - 1

3 - 2

4 - 3

5 - 5

6 - 8

f(n) = f(n - 1) + f(n - 2) (n > 2 일 경우) 의 점화식을 도출 할 수 있다.

1 / 10 01 / 101 100 / 1000 1010 1001 / 10000 10101 10010 10100 10001 / 100000 101000 101010 101001 100101 100100 100010 100001....

다이나믹 프로그래밍, 메모이제이션을 사용하여 풀어야 하는 문제이다.

2xN 직사각형을 1x2, 2x1, 2x2 타일로 채우는 경우의 수를 구를 2X(최대 1000)까지 구한다.

즉 반복되는 작업을 한다 -> 수열이 형성된다 라는 점을 기억해야한다.

1*2 -> A

2*1 -> B

2*2 -> C

라고 생각해보자

1) N이 1일 때

- B 한가지만 들어갈 수 있다.

- F(1) = 1

2) N이 2일 때

- AA, BB, C

- F(2) = 3

3) N이 3일 때

- AAB, BAA, CB, BC, BBB

- F(3) = 5

4) N이 4일 때

- AAAA, BBBB, AABB, BBAA, BAAB, AAA, CAA, BBC, CBB, BCB, CC 

- F(4) = 11

이 떄, N이 4 이상일 경우, F(N) = F(N - 1) + (F(N - 2) * 2)

의 일반항을 도출할 수 있고 이를 메모이제이션하여 출력해주면 된다.

문제의 반복성과 규칙성을 찾아내 일반항을 도출하는 것

-> 다이나믹 프로그래밍으로 해결할 수 있다.