백준(BOJ) 3866 풍선 수집(Python)

문제 내용

 

조건

 

2차원 DP 문제.

가로 길이는 전체 풍선의 개수, 세로 길이는 현재 로봇에 달려 있는 풍선의 개수로 2차원 DP 리스트를 설정했다.

당연히 풍선은 빨리 떨어지는 순으로 받아줘야 하고, 첫 풍선은 선택지 없이 집에서 출발해 받아줘야 한다.

그 다음부터 떨어지는 풍선에 대해서는 2가지의 선택지가 존재한다. 풍선을 집에 두고 받을 것인지, 그냥 받으러 갈 것인지.

이를 DP에 적용해주면 된다.

​

i가 전체 풍선의 개수만큼의 반복문의 인자, j가 로봇에 달릴 수 있는 풍선의 개수만큼의 반복문의 인자라고 하면

첫 번째 경우 풍선의 개수가 1개로 변하는 과정이므로 dp[1][i+1]=min(dp[1][i+1],dp[j][i]+p+x)라는 점화식을 세울 수 있다.

두 번째 경우 풍선의 개수가 (현재 풍선의 개수)+1로 변하는 과정이므로 dp[j+1][i+1]=dp[j][i]+abs(x-p)라는 점화식을 세울 수 있다.

​

이를 코드로 나타내면 아래와 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

while True:
    n=int(input())
    if n==0:
        break
    L=[]
    for i in range(n):
        L.append(list(map(int,input().split())))
    if L[0][0]>L[0][1]:
        print('NG',1)
        continue
    dp=[[0 for i in range(n+1)] for j in range(4)]
    dp[1][1]=L[0][0]
    t=L[0][1]
    flag2=0
    for i in range(1,n):
        x,y=L[i]
        flag=0
        for j in range(1,4):
            p=L[i-1][0]
            if dp[j][i]!=0:
                if abs(x-p)*(j+1)+t<=y and j<3:
                    flag=1
                    dp[j+1][i+1]=dp[j][i]+abs(x-p)
                if p*(j+1)+x+t<=y:
                    flag=1
                    if dp[1][i+1]==0:
                        dp[1][i+1]=dp[j][i]+p+x
                    else:
                        dp[1][i+1]=min(dp[1][i+1],dp[j][i]+p+x)
        if not flag:
            flag2=1
            print('NG',i+1)
            break
        t=y
    if not flag2:
        L2=[]
        for i in range(1,4):
            if dp[i][-1]:
                heapq.heappush(L2,dp[i][-1])
        print('OK',L2[0]+L[n-1][0])

문제를 푸는 데 2시간 정도 걸린 것 같다.

처음에 문제를 보고 2차원 DP가 아닐까 생각했지만 애초에 2차원 DP가 그리 자신이 없었던지라 1차원 DP로 풀어보려 애를 썼다.

그러나 1차원 DP로는 모든 케이스를 커버할 수 없다고 생각해 2차원 DP로 선회했고, 그 과정에서 시간이 많이 소요됐다.

여기까지 1시간 정도 걸린 것 같다.

​

위에서 설명한 알고리즘을 구현하고 제출을 했는데, 계속 '틀렸습니다'만 떴다.

대체 내가 뭘 잘못한 건가, 내 알고리즘의 어디가 문제인건가 싶어서 계속 들여다보고, 이리저리 고쳐보고 했는데도 해결이 안 되길래, 구글링을 통해 다른 사람의 solution code를 찾아봤다. 애초에 백준에서는 맞힌 사람이 15명인 문제라 한국어로 된 해설은 기대도 안 했고, 문제가 ICPC Regional Tokyo 2010 문제길래 일본 온라인 저지 사이트인 AOJ에서 문제를 찾아봤다.

​

파이썬 코드를 찾아봤는데 내 코드와 별반 다르지 않아서 다시 코드를 들여다보니 NG를 처리하는 조건문에 break가 빠져있는 것을 확인할 수 있었다. break가 빠져있어서 NG가 여러 번 출력될 수도 있었던 것이다.

​

코드 한 줄 때문에 1시간을 넘게 잡혀있었던 게 조금 억울하기도 하지만, 결국 내 실력이 부족했던 데에서 문제가 발생한 거라고 생각한다.

여러모로 도움이 많이 된 문제였다.