처음에 DP라는 말에 쉬운줄 알았지만
쿠폰과 쉬는 날을 보고 멘붕이 왔다.
오래 고민하다가 머릿속에서 꼬여서 포기하고 검색했다.
http://wookje.dance/2017/03/06/boj-13302-%EB%A6%AC%EC%A1%B0%ED%8A%B8/
http://wookje.dance/2017/03/06/boj-13302-%EB%A6%AC%EC%A1%B0%ED%8A%B8/
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include <iostream> #include <algorithm> #define n_ 106 #define INF 0x7fffffff using namespace std; int n, m; int dp[n_][n_]; bool chk[n_]; int main(void) { cin >> n >> m; for (int i = 0; i < m; i++) { int a; cin >> a; chk[a] = true; } for (int i = 1; i <= n; i++) { for (int j = 0; j < n; j++) { dp[i][j] = INF; } } dp[0][0] = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= i; j++) { //i번째 날 j개의 쿠폰 if (dp[i][j] == INF)continue; int now = dp[i][j]; if (chk[i + 1]) { dp[i + 1][j] = min(now, dp[i + 1][j]); } if (j >= 3) { dp[i + 1][j - 3] = min(dp[i + 1][j - 3], now); } dp[i + 1][j] = min(now + 10000, dp[i + 1][j]); for (int k = 1; k <= 3; k++) { dp[i + k][j + 1] = min(now + 25000, dp[i + k][j + 1]); } for (int k = 1; k <= 5; k++) { dp[i + k][j + 2] = min(now + 37000, dp[i + k][j + 2]); } } } int ans = INF; for (int i = 0; i < n; i++) { if (dp[n][i] < ans) { ans = dp[n][i]; } } cout << ans; } | cs |
'알고리즘 > PS' 카테고리의 다른 글
[백준 1005] ACM craft (0) | 2018.05.19 |
---|---|
[백준 1202] 보석도둑 (0) | 2018.05.18 |
[백준 7576] 토마토 (0) | 2018.05.18 |
[백준 2448] 별찍기 - 11 (0) | 2018.05.18 |
[백준 2447] 별찍기 - 10 (0) | 2018.05.18 |