서론
오늘의 코딩 테스트 문제는 '백준 1149번 RGB거리'다. 동적 프로그래밍(DP) 문제로, 조건을 만족하면서 최소 비용을 찾는 것이 핵심이다.
문제 분석
문제의 핵심은 다음과 같다:
•
N개의 집을 RGB 중 하나로 칠해야 함
•
인접한 집은 같은 색이면 안 됨
•
각 집마다 RGB 칠하는 비용이 다름
•
조건을 만족하는 최소 비용을 구해야 함
제한 사항:
•
2 ≤ N ≤ 1,000
•
비용은 1,000 이하의 자연수
접근 방식
DP로 접근했다. 각 단계에서 R, G, B를 선택했을 때의 최소 비용을 저장하고, 이전 단계의 결과를 이용해 현재 단계의 최소 비용을 계산한다.
알고리즘:
1.
2D 벡터로 각 집의 RGB 비용 저장
2.
결과를 저장할 2D 벡터 생성
3.
두 번째 집부터 순회하며 각 색상 선택 시 최소 비용 계산
•
R 선택 시: 이전 집의 G, B 중 최소값 + 현재 R 비용
•
G, B도 같은 방식으로 계산
4.
마지막 집에서 R, G, B 중 최소값이 답
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
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];
vector<vector<int>> results = costs;
for (int i = 1; i<N; i++)
{
for (int j=0; j<3; j++)
{
if (j==0)
results[i][j] += min(results[i-1][1], results[i-1][2]);
else if (j==1)
results[i][j] += min(results[i-1][0], results[i-1][2]);
else if (j==2)
results[i][j] += min(results[i-1][0], results[i-1][1]);
}
}
cout << *min_element(results.back().begin(), results.back().end()) << endl;
return 0;
}
C++
복사
구현 과정
구현은 간단했다. 입력 받고, DP 테이블 만들고, 점화식대로 계산하면 끝이다.
특이한 점은 이전 결과에서 현재 색과 같은 색을 제외하고 최소값을 찾는 부분이다.
처음에는 if-else로 구현했는데, 나중에 min 함수로 간단히 수정했다.
코드가 깔끔해져서 만족스럽다.
회고
이 문제로 새롭게 배운 건 없다. 그냥 전형적인 DP 문제다.
특이한 점이라면 이전 해답이 3개이고, 그 중 자신의 인덱스를 제외하고 카운트한다는 정도?
앞으로 DP 문제를 더 많이 풀어봐야겠다. 특히 2차원 이상의 DP 테이블을 사용하는 문제들.
