티스토리 뷰
버스를 타는 버스 정기권과 버스와 기차를 모두 타는 전체 정기권이 기간 별로 주어지고, 각 날 마다 버스와 기차 타는 회수가 주어졌을 때, $N$일 동안 버스와 기차를 타는 최소 비용을 구하는 문제다.
문제에서 정기권의 기간과 요금, 그리고 단일 회수로 탑승할 때의 비용은 입력과 상관없이 항상 같게 정해져있다. Dynamic Programming을 생각해볼 수 있다.
D[i][j] = i번째 날 까지 버스와 기차를 타고, 현재 남은 버스 정기권의 기간이 j일 때 최소 비용
위와 같이 다이나믹 배열을 정의하자. 이처럼 정의하는 이유가 있다. 전체 정기권을 산 경우 정기권 기간내에는 고려할 사항이 아무 것도 없지만, 버스 정기권을 산 경우 정기권 기간 내에 전체 정기권을 사는게 더 이익일 수 있기 때문이다.
위 처럼 정의했을 때, 점화식은 직관적이게 생각 가능하며 시간복잡도는 $O(ND)$가 된다. 여기서 $D$는 정기권의 최대 기간이며 문제에서 $D \leq 30$이다.
'ICPC > 2014 대전' 카테고리의 다른 글
L. Two Yachts (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 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- idea
- moore
- Divide & Conquer
- Greedy Method
- Knuth Optimization
- vote
- dynamic programming
- z-trening
- optimization
- IOI2011
- BOI 2001
- Splay Tree
- Segment tree
- Boyer
- BOI
- majority
- Algorithm
- IOI2012
- IOI2014
- BOI 2009
- Dijkstra
- ioi
- Dynamic Pramming
- Tree
- HackerRank
- Boyer-Moore Majority Vote Algorithm
- TRIE
- IOI2013
- Parametric Search
- USACO
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함