Backjoon Online Judge
"1149번 : 피보나치 수 3" 문제입니다.
문제 링크 : https://www.acmicpc.net/problem/1149
일단 문제에서 비용의 최솟값을 출력하기 위해 모든 선택 경우에서 나올 수 있는 비용을 알고 있어야 하고, 이를 구현하기 위해 DP를 이용하였습니다.
이때 문제의 조건을 만족하려면 현재 집을 칠해야 할 색은 이전집에 칠한 색깔이 아닌 색만을 칠할 수 있다는 사실을 확인했고 배열을 통해 검사하는 범위를 줄이기로 했습니다.
- 먼저 N <= 1000이므로 모든 집의 색깔을 저장할 3*1000의 배열을 선언하여 그 배열에 저장하였습니다.
- 이후 N에 따라 검사 결과를 저장할 total 배열에 비용의 최솟값을 저장했습니다. 이때 비용의 최솟값을 저장하기 위해 algorithm헤더에 포함된 min함수를 이용하였습니다.
- 비용은 현재 집에 칠할 색깔 별로 비용을 각각 구했으며 비용은 이전 집에 칠한 색깔의 최솟값 중 현재 집에 칠할 색깔과 같지 않은 최솟값 중 작은것을 더했습니다.
코드는 C++로 작성하였습니다.
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 | #include <iostream> #include <algorithm> #define MAX 1000 using namespace std; int main() { int N, miniMum; int cost[MAX][3] = { 0 }; int total[MAX][3] = { 0 }; cin >> N; for(int i = 0; i < N; i++) { cin >> cost[i][0] >> cost[i][1] >> cost[i][2]; } total[0][0] = cost[0][0]; total[0][1] = cost[0][1]; total[0][2] = cost[0][2]; for (int i = 1; i < N; i++) { total[i][0] = cost[i][0] + min(total[i - 1][1], total[i - 1][2]); total[i][1] = cost[i][1] + min(total[i - 1][0], total[i - 1][2]); total[i][2] = cost[i][2] + min(total[i - 1][0], total[i - 1][1]); } cout << min(total[N - 1][0], min(total[N - 1][1], total[N - 1][2])); return 0; } | cs |
'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글
| 2579번 : 계단 오르기 (0) | 2018.05.05 |
|---|---|
| 1932번 : 숫자삼각형 (0) | 2018.05.01 |
| 1003번 : 피보나치 함수 (0) | 2018.04.01 |
| 2749번 : 피보나치 수 3 (0) | 2018.04.01 |
| 2748번 : 피보나치 수 2 (0) | 2018.04.01 |