티스토리 뷰

ICPC/2014 대전

K. Travel Card

전명우 2014.11.10 11:55

버스를 타는 버스 정기권과 버스와 기차를 모두 타는 전체 정기권이 기간 별로 주어지고, 각 날 마다 버스와 기차 타는 회수가 주어졌을 때, $N$일 동안 버스와 기차를 타는 최소 비용을 구하는 문제다.


문제에서 정기권의 기간과 요금, 그리고 단일 회수로 탑승할 때의 비용은 입력과 상관없이 항상 같게 정해져있다. Dynamic Programming을 생각해볼 수 있다.


D[i][j] = i번째 날 까지 버스와 기차를 타고, 현재 남은 버스 정기권의 기간이 j일 때 최소 비용


위와 같이 다이나믹 배열을 정의하자. 이처럼 정의하는 이유가 있다. 전체 정기권을 산 경우 정기권 기간내에는 고려할 사항이 아무 것도 없지만, 버스 정기권을 산 경우 정기권 기간 내에 전체 정기권을 사는게 더 이익일 수 있기 때문이다.


위 처럼 정의했을 때, 점화식은 직관적이게 생각 가능하며 시간복잡도는 $O(ND)$가 된다. 여기서 $D$는 정기권의 최대 기간이며 문제에서 $D \leq 30$이다.


코드 보기


'ICPC > 2014 대전' 카테고리의 다른 글

L. Two Yachts  (2) 2014.11.10
K. Travel Card  (2) 2014.11.10
J. Tours  (0) 2014.11.10
I. Three Squares  (0) 2014.11.10
H. String Transformation  (0) 2014.11.10
G. Road Repair  (0) 2014.11.10
댓글
댓글쓰기 폼