[파이썬] 백준 14550 : 마리오 파티 (골드5)

[파이썬] 백준 14550 : 마리오 파티 (골드5)

14550번: 마리오 파티

---

문제

---

풀이

0. 방향성 생각

• 순방향 DP
• 최대값을 구하고 값이 arr가 음수인 부분이 있으므로 DP 초기화를 -1e9로 시켜준다

1. 입력

while True:
    
    info = list(map(int,input().split()))

    if info == [0]: break
    n,dice,chance = info

    arr = []
    while len(arr) < n:
        arr.extend(list(map(int,input().split())))
    arr = [0] + arr + [0]

• 입력 받는게 조금 특이하다.
• 기본 정보를 받고 0을 받은게 아니면 계속 진행
• arr 길이가 n보보다 작은 경우에 계속 받는다.
• arr[i번째 위치]를 맞추기 위해서 양 끝에 0을 붙인다.

2. DP 테이블

    dp = [[-1e9]*(n+2) for _ in range(chance+1)]

    dp[1][:dice+1] = arr[:dice+1]
    for stage in range(1,chance):
        for x in range(stage,n+1):
            for step in range(1,dice+1):
                if x+step > n:
                    dp[stage+1][-1] = max(dp[stage+1][-1],dp[stage][x])
                else:
                    dp[stage+1][x+step] = max(dp[stage+1][x+step],dp[stage][x]+arr[x+step])
    print(dp[-1][-1])

• dp[1회] 값들은 한 번 던져서 갈 수 있는데 까지 arr과 똑같이 채운다.
• dp[stage회][x번째]에서는 현재 저장된 값과 x에서 step 만큼 주사위를 던져서 온 값 중 큰 값을 선택한다.
• 만약 x+step이 n보다 큰 경우에 별을 먹게되고 이 경우에는 코인을 먹지 못한다.
• dp[-1][-1] : 전부 던진 후 별을 먹은 경우 최대값 저장

 

 

---

전체코드

while True:
    
    info = list(map(int,input().split()))

    if info == [0]: break
    n,dice,chance = info

    arr = []
    while len(arr) < n:
        arr.extend(list(map(int,input().split())))
    arr = [0] + arr + [0]

    dp = [[-1e9]*(n+2) for _ in range(chance+1)]

    dp[1][:dice+1] = arr[:dice+1]
    for stage in range(1,chance):
        for x in range(stage,n+1):
            for step in range(1,dice+1):
                if x+step > n:
                    dp[stage+1][-1] = max(dp[stage+1][-1],dp[stage][x])
                else:
                    dp[stage+1][x+step] = max(dp[stage+1][x+step],dp[stage][x]+arr[x+step])
    print(dp[-1][-1])

 

코멘트

이제 이런 순방향 DP는 쉽다...