https://www.acmicpc.net/problem/17404
문제 풀이
이 문제는 1번 집과 N번 집의 색을 고려해 문제를 해결해야하기 때문에 조금 까다로웠다.
2중 for문을 통해
1번 집의 색을 고정 시킨 후 dp를 통해서 비용의 최솟값을 구하면 되는 문제이다.
소스 코드
#include <iostream>
using namespace std;
#define MAX 1001 * 1001
int cost[1001][3];
int dp[1001][3];
int ans = MAX;
int main() {
int N;
cin >> N;
//Cost 세팅
for (int i = 1; i <= N; i++)
cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
for (int rgb = 0; rgb <= 2; rgb++) { // rgb = 1번 집의 색
// 1번집에 지정된 색 이외의 색은 MAX로 지정하여 dp할때 선택되지 않도록 함
for (int i = 0; i <= 2; i++) {
if (i == rgb)
dp[1][i] = cost[1][i];
else
dp[1][i] = MAX;
}
// DP
for (int i = 2; i <= N; i++) {
dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
}
// 1번집 색과 N번집 색이 겹치지 않게 함
for (int i = 0; i <= 2; i++) {
if (i == rgb) continue;
else ans = min(ans, dp[N][i]);
}
}
cout << ans;
}
'알고리즘' 카테고리의 다른 글
[백준] 10942번 팰린드롬? C++ 문제풀이 (0) | 2024.01.12 |
---|---|
[백준] 27172번 수 나누기 게임 C++ 문제풀이 (1) | 2024.01.11 |
[백준] 9252번 LCS 2 C++ 문제풀이 (0) | 2024.01.09 |
[백준] 9251번 LCS C++ 문제풀이 (0) | 2024.01.08 |
[백준] 2467번 용액 C++ 문제풀이 (1) | 2024.01.08 |