파이썬으로 풀어보는 백준 13302번: 리조트

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

13302번: 리조트

 

내 풀이:

N, M = map(int,input().split())
plan = [True] * (N+1)
max_ticket = (N//5)*2 + (N % 5)//3 + 1
state = [[1000000] * max_ticket for _ in range(N+1)]
state[0][0] = 0
if M > 0:
    for i in list(map(int,input().split())):
        plan[i] = False
 
for day, p in enumerate(plan[1:], 1):
    for i in range(max_ticket):
        if state[day-1][i] < 1000000:
            if p:
                if i >= 3:
                    state[day][i-3] = min(state[day][i-3], state[day-1][i])
                else:
                    state[day][i] = min(state[day-1][i] + 10000, state[day][i])
 
            else:
                state[day][i] = min(state[day-1][i], state[day][i])
 
        if day-3 >= 0:
            if state[day-3][i] < 1000000:
                state[day][i+1] = min(state[day-3][i] + 25000, state[day][i+1])
 
        if day-5 >= 0:
            if state[day-5][i] < 1000000:
                state[day][i+2] = min(state[day-5][i] + 37000, state[day][i+2])
 
ans = 1000000
 
for j in range(max_ticket):
    ans = min(ans, state[N][j])
print(ans)

Python3, 68ms

문제를 읽자마자 DP 문제라는 것은 바로 알아차렸으나 문제 조건에서 티켓이 상당히 까다롭게 작용해서 어떻게 처리해야 하나 고민을 많이 한 문제이다. 사람들이 평가하는 난이도나 정답률에 비해 체감되는 난이도는 꽤 높았다. 결과적으로 문제를 풀기 위해 2차원 배열에서 행에는 날짜를, 열에는 티켓 개수를 대입하여 해결했다. 10 3 / 2 5 6이라는 입력 예제에 대해 62000이 출력되어야 하는데 65000이 출력되어 첫 제출 시 오답 판정을 받았다. 내용은 즉 3일 혹은 5일이라는 기한이 끝나는 날 리조트에 있지 않은 경우를 빼먹은 것이다. DP의 경우 어떤 값을 저장할 것이냐가 가장 중요한데 이번 문제의 경우 처음에는 티켓의 개수만큼 배열을 키운다는 점에서 시간 초과를 걱정하여 쉽게 코딩에 들어가지 못하였는데 최대 100 * 40 크기의 배열이 나오므로 생각보다 크기가 크지 않아 시간 초과가 나지 않은 것 같다.