EDOC 2024-1 3회차 과제 (동적 계획법 알아보기 1)

11-1. 동적 계획법 알아보기

 

084. 1로 만들기 (백준 1463번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
num = [0 for _ in range(n + 1)]

for i in range(2, n + 1):
    num[i] = num[i - 1] + 1
    if i % 2 == 0:
        num[i] = min(num[i], (num[i // 2] + 1))
    if i % 3 == 0:
        num[i] = min(num[i], (num[i // 3] + 1))

print(num[n])

이전에 풀었던 문제. 간단한 다이나믹 문제였다. (정답)

 

---

 

085. 퇴사 (백준 14501번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
data = [[0, 0] for _ in range(n + 1)]
dp = [0 for _ in range(n + 2)]

for i in range(1, n + 1):
    a, b = map(int, input().split())
    data[i][0] = a
    data[i][1] = b

for i in range(n, 0, -1):
    if (i + data[i][0] - 1) <= n:
        dp[i] = max(data[i][1] + dp[i + data[i][0]], dp[i + 1])
    else:
        dp[i] = dp[i + 1]
    
print(dp[1])

처음에 이걸 어떻게 다이나믹 프로그래밍으로 풀지??? 하면서 고민하다가 도저히 모르겠어서 책에서 힌트를 얻었다. 점화식 dp를 i번째 날부터 퇴사일까지 벌 수 있는 최대 수입으로 한다는 내용을 보고 아 그래서 다이나믹이구나!!를 깨닫고 풀었다. 사실상 책이 다한 ^__^ (정답)

 

---

 

086. 이친수 (백준 2193번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0 for _ in range(n + 1)] for _ in range(2)]

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

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

print(dp[0][n] + dp[1][n])

노트에 n을 1부터 하나씩 키워가면서 적어보다보니 0으로 끝나는 수와 1로 끝나는 수를 구분해서 카운트해야 한다는 것을 알 수 있었다. dp 배열에 저장하되, dp를 2차원 배열로 만들어 0으로 끝나는 이친수의 개수를 dp[0]에 저장하고 1로 끝나는 이친수의 개수를 dp[1]로 저장하였다. 점화식은 다음과 같다.

dp[0][n] = dp[0][n - 1] + dp[1][n - 1]   (0은 아무 조건없이 올 수 있다)

dp[1][n] = dp[0][n - 1]   (1은 앞의 수가 0이어야만 올 수 있다)

(정답)

 

그런데 이 문제에서의 수열 dp가 피보나치 수열과 동일하다는 것을 이독 스터디를 통해서 알게 되었다. 그 이유가 궁금해서 질문게시판을 찾아봤다...ㅎ 찾아서 내 나름대로 이해한 것이 다음과 같다.

n자리 이친수의 개수를 f(n)이라고 하자. 어떤 이친수의 마지막 수는 0일수도 있고 1일수도 있다.

이친수의 마지막 수가 0인 경우 → 0 앞의 (n-1)자리가 이친수여야 한다. → f(n-1)

이친수의 마지막 수가 1인 경우 → 1 앞에는 무조건 0이 와야 하고, 10 앞의 (n-2)자리가 이친수여야 한다. → f(n-2)

⇒ f(n) = f(n-1) + f(n-2) (피보나치 수열)