참고 교재

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)

실전 문제 1 - 1로 만들기

탐욕법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())

result = 0

while n != 1:
    if n % 5 == 0:
        n //= 5
    elif n % 3 == 0:
        n //= 3
    elif n & 1 != 0:
        n //= 2
    else:
        n -= 1

    result += 1

print(result)

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
result = 0
dp = [0] * 30001

dp[0], dp[1] = 0, 0

for i in range(2, n + 1):
    x = [dp[i - 1]]

    if i & 1 == 0:
        x.append(dp[i // 2])
    elif i % 3 == 0:
        x.append(dp[i // 3])
    elif i % 5 == 0:
        x.append(dp[i // 5])

    dp[i] = min(x) + 1

print(dp[n])

점화식
$f(n) = min(f(n-1), f(n\div2), f(n\div3), f(n\div5) ) + 1\ (n \geq 2)$
단, 함수 f의 인자가 정수가 아닌 경우 연산에 포함하지 않음

실전 문제 2 - 개미 전사

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
depots = list(map(int, input().split()))

dp = [0] * 100
dp[0] = depots[0]
dp[1] = max(depots[0], depots[1])

for i in range(2, n):
    dp[i] = max(dp[i - 1], dp[i - 2] + depots[i])

print(dp[n - 1])

점화식
$f(n) = max(f(n-1),f(n-2)+A[n])\ (n \geq 2)$
인덱스가 0부터 시작하는 것에 유의하여 f(0)은 n이 1일 때 상황임.

실전 문제 3 - 바닥 공사

1
2
3
4
5
6
7
8
9
n = int(input())

dp = [0] * 1001
dp[1], dp[2] = 1, 3

for i in range(3, n + 1):
    dp[i] = dp[i-1] + dp[i-2] * 2

print(dp[n])

점화식
$f(n)=f(n-1)+2 \times f(n-2) (n \geq 3)$

실전 문제 4 - 효율적인 화폐 구성

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n, m = map(int, input().split())
currencies = []
dp = [10001] * (m + 1)
dp[0] = 0

for i in range(n):
    c = int(input())
    if c <= m:
        currencies.append(c)

for k in currencies:
    for i in range(1, m + 1):
        if dp[i - k] != 10001:
            dp[i] = min(dp[i], dp[i - k] + 1)

if dp[m] != 10001:
    print(dp[m])
else:
    print(-1)

점화식
$f(i -k)=10,001인\ 경우, f(i-k)가\ 존재하지\ 않는다고\ 정의한다.$

$f(i-k)\ 이\ 존재할\ 경우,f(i)=min(f(i),f(i-k)+1)$

$f(i-k)가\ 존재하지\ 않을\ 경우,f(i)=10,001$