2차원 DP 문제였지만 3차원 DP로 풀어서 코드가 복잡해졌다.
N번째 집의 경우 1번째 집의 색깔과 겹치면 안되기 때문에 이 조건을 처리하기 위해 1차원 더 추가해서 첫번째 집에 어떤 색깔을 칠했는지 캐싱했는데, 2차원 배열로 선언한 뒤 첫번째 집을 R, G, B 각각 칠했을 경우에 대해 각각 DP 로직을 수행해서 그중 가장 비용이 작은 값을 구해도 된다. 2차원 배열로 선언하는 방식이 캐싱하는데 필요한 메모리를 절약할 수 있다.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 987654321
int memo[1000][3][3];
void bottomup(vector<vector<int>>& costs, int N)
{
int R = 0;
int G = 1;
int B = 2;
memo[0][R][R] = costs[0][R];
memo[0][G][G] = costs[0][G];
memo[0][B][B] = costs[0][B];
for(int i=1; i<N; i++)
{
if(i + 1 == N)
{
memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];
memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];
memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
}
else
{
memo[i][R][R] = min(memo[i-1][R][G], memo[i-1][R][B]) + costs[i][R];
memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];
memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
memo[i][G][G] = min(memo[i-1][G][R], memo[i-1][G][B]) + costs[i][G];
memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];
memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
memo[i][B][B] = min(memo[i-1][B][R], memo[i-1][B][G]) + costs[i][B];
}
}
int result = INF;
for(int first = R; first<=B; ++first)
{
for(int here = R; here<=B; ++here)
{
if(here==first) continue;
result = min(result, memo[N-1][first][here]);
}
}
cout << result;
}
int main(void)
{
fill_n(memo[0][0], 1000*3*3, INF);
int N;
cin >> N;
vector<vector<int>> costs(N, vector<int>(3));
for(int i=0; i<N; ++i)
{
for(int j=0; j<3; ++j)
{
cin >> costs[i][j];
}
}
bottomup(costs, N);
return 0;
}
'알고리즘 > BOJ' 카테고리의 다른 글
백준 9655번: 돌 게임 (0) | 2025.09.16 |
---|---|
백준 2468번: 안전 영역 (3) | 2025.08.04 |
백준 1057번: 토너먼트 (0) | 2025.08.04 |
백준 25206번: 너의 평점은 (0) | 2025.03.21 |
백준 7569번: 토마토 (0) | 2023.08.18 |