BOJ 17404, RGB거리 2
ProblemSolving ·이번 문제는 DP문제입니다.
풀이
각 집마다 페인트칠을 하는데 그 값의 최솟값을 구하는 문제입니다.
이웃끼리 다른색이어야하고 또 시작집과 마지막집이 다른색이어야하는 문제입니다.(집들이 동그랗게 모여있다고 하면 이해할 수 있으시겠죠?)
우선 arr배열에 각 집이 무슨 색으로 칠할때 얼마인지를 입력을 받았습니다.
그 다음 포문이 핵심입니다. k의 변수는 시작집의 색을 무슨 색으로 칠할지 입니다. 시작칠하는 색과 같은 색을 dp[1][i]배열에 저장해줘야겠죠?
시작하는 색과 첫번째 페인트색이 다르다는 것 자체가 모순이기때문에 무한대 값을 저장해줘 연산이 되지 않게 막아주겠습니다.
그 다음 dp배열에 i번째 집에서 1이라는 색을 칠할때가 dp[i][1]입니다. 이 값은 dp[i-1][2] 또는 dp[i-1][3] 에 arr[i][1]을 칠한 값이 나오겠죠.
이런 식으로 n까지 연산을 해주고 첫번째 색과 마지막 색이 다른 dp[n][i] 값중에 최솟값을 찾아 출력해주면 됩니다!!!
#include<algorithm>
#include<cmath>
#include<stdio.h>
int arr[1001][4];
int dp[1001][4];
int n, Min = 1e6;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 3; j++)
scanf("%d", &arr[i][j]);
for (int k = 1; k <= 3; k++)
{
for (int i = 1; i <= 3; i++)
{
if (k == i)
dp[1][i] = arr[1][i];
else
dp[1][i] = 1001;
}
for (int i = 2; i <= n; i++)
{
dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + arr[i][1];
dp[i][2] = min(dp[i - 1][1], dp[i - 1][3]) + arr[i][2];
dp[i][3] = min(dp[i - 1][2], dp[i - 1][1]) + arr[i][3];
}
for (int i = 1; i <= 3; i++)
{
if (i == k)
continue;
Min = min(Min, dp[n][i]);
}
}
printf("%d\n", Min);
return 0;
}