chogahui05   4년 전

이문제.. 대회 당일에는 많이 푸신 걸로 알고 있는데.. 생각보다 머리가 아프네요.

저는 이렇게 생각하고 풀었습니다.


(1) 같은 패스는 특정한 어느 날에 여러 개를 가지고 있을 수 있다.

그러니까 패스는 항상 살 수 있다..


예를 들어서 7일차에 7일치 버스 pass를 끊었습니다.

그리고 12일차에 또 7일치 버스 pass를 끊었습니다. (7일차에 산 7일치 pass가 남았는데도)

그것도 가능한 건지요..


저는 (1)이 가능하다고 생각하고..

x일치일 때 총 지불한 가격의 최솟값은

a = d[x] (이전에 7일치, 30일치를 샀을 때까지 고려한 최솟값)

b = d[x-1] + 패스를 안 샀을 때 지불한 금액

c = d[x-1] + 6

d = d[x-1] + 1일치 버스 패스를 샀을 때 지불한 금액 

d[x] = a,b,c,d 중 최솟값.


그리고 n일치 pass를 구할 때에는

패스를 구매한 가격을 구해놓고, n일치를 돌려가면서 update를 했는데요.

(4번부터 7번까지)


이렇게 돌리면 모든 부분 문제가 포함된다고 생각하고 돌렸습니다.

채점하자마자 틀렸다고 하면 모르겠습니다만..

90%대에서 틀렸다고 하니.. 머리가 아파집니다.


다른 조건이 더 붙어 있는 것인지.

아니면 제가 놓친 케이스가 있는건지. 궁금합니다..

댓글을 작성하려면 로그인해야 합니다.