인프런 커뮤니티 질문&답변

31883번: FA수의 진 (acmicpc.net)

백준의 31883 문제를 DP로 풀면 깔끔하게 풀릴 수 있다고 생각해서 DP로 풀었습니다. 하지만 풀고나서 문제 카테고리가 그리디로 있는 걸 확인하고 그리디로 풀으니 더 코드가 깔끔하게 풀리는 경험을 했습니다.

그리디로 풀린다는 판단은 이 문제에서 어떻게 생각해야 되는 걸까요? 그리고 그리디 문제다 하는 판단 근거 유추를 어떻게 해야 하는지 강의에 있는 내용 외로 보충 설명 해주시면 감사하겠습니다.

아래는 DP로 풀은 코드 입니다.

import sys
input = sys.stdin.readline

N = int(input())
times = [list(map(int, input().split())) for _ in range(N)]
memo = [[0] * 2 for _ in range(N)]

memo[0][0] = times[0][0]
memo[0][1] = times[0][1]

for i in range(1, N):
    t1 = memo[i-1][0]
    tmp = t1 % (times[i][2] + times[i][3])
    if tmp >= times[i][2]:
        t1 += times[i][2] + times[i][3] - tmp
    t1 += times[i][0]

    t2 = memo[i-1][1]
    tmp = t2 % (times[i][2] + times[i][3])
    if tmp >= times[i][2]:
        t2 += times[i][2] + times[i][3] - tmp   
    t2 += times[i][0]

    cross1 = min(t1, t2)

    t3 = times[i][1] + memo[i-1][0]
    t4 = times[i][1] + memo[i-1][1]

    cross2 = min(t3, t4)

    memo[i][0] = cross1
    memo[i][1] = cross2

print(min(memo[N-1]))