BOJ 1로만들기2, 포도주시식

1. BOJ 12852 1로만들기2

실버 1, DP, 그래프탐색 

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

코드

N = int(input())
dp = [0]*(10**6+1)
ans = [N]
for i in range(2,N+1):
    if i%6==0:
        dp[i] = (min(dp[i//3]+1, dp[i//2]+1))
    elif i%3==0:
        dp[i] = (min(dp[i//3]+1, dp[i-1]+1))
    elif i%2==0:
        dp[i] = (min(dp[i//2]+1, dp[i-1]+1))
    else:
        dp[i] = (dp[i-1]+1)
print(dp[N])
while N!=1:
    if N%6==0:
        if dp[N//3]<=dp[N//2]:
            ans.append(N//3)
            N = N//3
        else:
            ans.append(N//2)
            N = N//2
    elif N%3==0:
        if dp[N//3]<=dp[N-1]:
            ans.append(N//3)
            N = N//3
        else:
            ans.append(N-1)
            N = N-1
    elif N%2==0:
        if dp[N//2]<=dp[N-1]:
            ans.append(N//2)
            N = N//2
        else:
            ans.append(N-1)
            N = N-1
    else:
        ans.append(N-1)
        N = N-1
 
for i in ans:
    print(i, end=' ')

설명

입력으로 어떤 수가 주어지면, (1) 3으로 나누기, (2) 2로 나누기, (3) 1 빼기를 조합하여 가장 적은 연산으로 입력을 1로 만드는 것이 목표이다. 

해당 문제는 DP로 풀었다. dp배열을 생성하고, 각각은 0부터 10^6까지 각 숫자에서 할 수 있는 최소한의 연산이다.

DP문제는 이후 값을 살피거나, 전체 탐색을 해서 푸는 것이 아니라 이전 상태를 활용하는 것이 포인트다. 

따라서 해당 문제는 N이 1이 될 때까지, N이 3으로 나눠지면 dp[N//3]+1 과 dp[N-1]+1 중 최솟값을 저장한다. 그 이유는 1을 먼저 빼주었을 때 연산이 적어지는 경우가 있기 때문인데, 대표적인 예시가 10이다. 
(10 -> 9 -> 3 -> 1) 
N이 2로 나눠질 때도 마찬가지로 dp를 저장한다. 

하지만 여기서 고려해줘야 하는 것이 있었는데, N이 6으로 나눠질 때였다. N이 6으로 나눠지는 경우 3으로도 2로도 나눌 수 있으므로 dp[N//3]과 dp[N//2]를 비교해준다. (처음에 고려해주지 않았다가 60%에서 틀렸다..) 

결론은 재밌는 문제였다. 

 

2. BOJ 2156 포도주시식

실버 1, DP 

나는 유독 DP문제가 재밌다. (그래프탐색도 좀 풀어야 할 텐데ㅠㅠ편식...)
DP는 어떻게 하면 더 문제를 빨리, 코드는 짧게 해결할 수 있을까 아이디어를 생각하는 과정이 좋다. 

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

코드

import sys
input = sys.stdin.readline
N = int(input())
arr = []
for i in range(N):
    arr.append(int(input()))
dp = arr.copy()
 
if N>3:
    dp[1] += arr[0]
    dp[2] += max(arr[0], arr[1])
    for i in range(3, N):
        dp[i] += max(dp[i-2], max(dp[:i-2])+arr[i-1])
elif N==2:
    dp[1] += arr[0]
elif N==3:
    dp[1] += arr[0]
    dp[2] += max(arr[0], arr[1])
else:
    pass
print(max(dp))

설명

6, 10, 13, 9, 8, 1 순서대로 포도주가 담겨있다. 연속해서 3잔은 마시지 못하고, 최대한 많이 마시도록 하는 것이 목표이다. 

이는 계단오르기 문제와 매우 흡사해서 쉽게 풀렸다. 오히려 계단오르기가 더 까다롭지 않았을까? (역시 계단오르기는 실버3 문제가 아니었다..!) 

문제 해결방법은 간단했다.  dp[i] = arr[i] + max(dp[i-2], max(dp[:i-2])+arr[i-1]) 

처음엔 dp[i] = arr[i] + max(dp[i-2], dp[i-3]+arr[i-1]) 을 생각했었다. 좌측은 1전 포도주는 건너뛰는 경우고, 우측은 3전 포도주와 1전 포도주를 마시는 경우다 (dp[i]는 i번째 포도주는 마신다는 가정인데, 최대 연속 2잔까지만 마실 수 있으므로). 하지만 이는 다음과 같은 반례가 있었다. 

6 10 10 1 1 10 10  정답:40 예측값:31

따라서 무조건 1전 포도주 또는 2전 포도주를 마시는 것이 아니라, 1전 포도주와 2전까지의 최댓값을 마시도록 코드를 수정했다. 더 좋은 아이디어가 분명 있을 것 같은데 궁금하다.