백준 14720: 우유 축제(DP) **

www.acmicpc.net/problem/14720

14720번: 우유 축제

 

마시는 규칙 : 처음은 무조건 딸기

딸기--> 초코--> 바나나 -->딸기 순으로 먹어야 함.

첫째 줄에 우유 가게의 수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄에는 우유 가게 정보가 우유 거리의 시작부터 끝까지 순서대로 N개의 정수로 주어진다.

우유 가게마다 마시거나(1) 마시지 않거나(0). 한번 지나간 가게는 돌아갈 수 없음.

0 : 딸기우유만을 파는 가게,

1 : 초코우유만을 파는 가게,

2 : 바나나우유만을 파는 가게

 

풀이 :

stores = list(map(int,input().split()))

현재 먹어야하는 우유를 mod3 정수로 나타냄.

가게를 지날 때마다 현재 먹을 수 있는 지 체크/ 먹었다면 현재 먹어야 하는 우유를 넘겨준다.

 

def solve(stores):
    milk = (0,1,2)
    curr_milk = 0 # 현재 먹어야하는 우유(딸기 우유로 시작)
    ans = 0
    for store in stores: # 방문한 store에서 curr_milk를 팔면
        if store==curr_milk: 
            ans+=1
            curr_milk=(curr_milk+1)%3 #다음 우유를 저장
    return ans


if __name__=='__main__':
    num = int(input())
    stores = list(map(int,input().split()))
    print(solve(stores))

 

-----------------------------------------------------------

문제가 단순해서 저 방법으로 패스했지만, 저렇게 하면 안된다. 때로는 건너뛰고 다음 걸 먹는 게 더 최적일 때도 있을텐데, 저 방법은 그냥 먹기 때문. (그렇지만 먹는 순서가 정해져있기 때문에 무조건 먹을 수 있는 게 먹는 게 이득이긴함..?)

DP를 탑다운 방식으로 분류돼있었는데 너무 쉽게 풀려서 찾아보니, 다음과 같은 방식을 찾았다.

 

dp[n][milk] = n번째 가게에서 마지막으로 먹은 우유가 index일 때 섭취한 최대 우유의 수
(출처: https://mygumi.tistory.com/223 [마이구미의 HelloWorld])

아래 코드는, 위 풀이를 참고하여 다시 작성한 코드이다.

def solve(T,stores):
    # i번째 가게에서 마지막으로 먹은 우유가 index일 때 섭취한 최대 우유의 수
    dp = {i:[0,0,0] for i in range(T)}
    # 딸기우유를 가장 먼저 먹어야 하므로, 딸기우유를 파는 데서 시작한다.
    start = stores.index(0)
    dp[start][0]=1
    for i in range(start+1,T):
        # i번째 가게가 파는 우유
        milk = stores[i]
        # 가장 최근 정보를 업데이트
        dp[i] = dp[i-1].copy()
        # 이전 순서의 우유를 먹었을 때에만, 현재 우유를 시도할 수 있다.
        if dp[i][(milk-1)%3] != 0:
            # 현재 우유를 먹느냐, 안 먹느냐
            dp[i][milk] = max(dp[i-1][(milk-1)%3]+1, dp[i-1][milk]) 
    return max(dp[T-1])


if __name__=='__main__':
    T = int(input())
    stores = list(map(int,input().split()))
    ans = solve(T,stores)
    print(ans)