250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- clustering
- MinHeap
- dfs
- 그래프 이론
- image processing
- canny edge detection
- Mask Processing
- 강화학습
- AlexNet
- object detection
- BFS
- opencv
- 인공지능
- SIFT
- 백준
- 딥러닝
- 머신러닝
- C++
- dynamic programming
- Reinforcement Learning
- DP
- Python
- exists
- edge detection
- IN
- sklearn
- TD
- MySQL
- classification
- machine learning
Archives
- Today
- Total
JINWOOJUNG
[ DP - 1149 ] RGB거리(C++) 본문
728x90
반응형
문제
접근법
DP 문제이기에 직접 하나하나 해 보면서 규칙을 찾고자 하였다. 하지만, 색상에 따른 Cost를 기준으로 규칙을 찾기에는 각 Cost는 변경되고, 동일한 Cost에 대한 처리가 힘들어 포기하였다.
Cost가 결정되는 기준은 결국 각각의 집이 칠하고자 하는 RGB색상에 의해 결정된다.
집의 색상을 결정하는 규칙은 결국 1번째 집부터 시작하여 다음집과 색상이 안겹치면 된다. 이 점에서 나올수 있는 경우의 수를 생각 해 보면, 다음 집의 색상이 R이 되기 위해선 이전에는 G,B가 되어야 한다. 다음 집의 색상이 B이 되기 위해선 이전에는 R,G가 되어야 하며, 다음 집의 색상이 G이 되기 위해선 이전에는 R,B가 되어야 한다.
for (s32_I = 1; s32_I <= s32_N; s32_I++)
{
cin >> ars32_Cost[0] >> ars32_Cost[1] >> ars32_Cost[2];
ars32_House[s32_I][0] = min(ars32_House[s32_I - 1][1], ars32_House[s32_I - 1][2]) + ars32_Cost[0];
ars32_House[s32_I][1] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][2]) + ars32_Cost[1];
ars32_House[s32_I][2] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][1]) + ars32_Cost[2];
}
따라서 각각의 색상에 따른 최소비용을 매번 계산한 후 최종적으로 가장 비용이 적은 것을 선택하면 된다.
정답
#include<iostream>
#include<algorithm>
using namespace std;
int32_t ars32_House[1001][3]; // 각각의 색으로 칠했을 때의 최소 비용을 저장
int32_t ars32_Cost[3]; // 각 집의 색상에 따른 비용 저장
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int32_t s32_N, s32_I;
cin >> s32_N;
ars32_House[0][0] = 0;
ars32_House[0][1] = 0;
ars32_House[0][2] = 0;
for (s32_I = 1; s32_I <= s32_N; s32_I++)
{
cin >> ars32_Cost[0] >> ars32_Cost[1] >> ars32_Cost[2];
ars32_House[s32_I][0] = min(ars32_House[s32_I - 1][1], ars32_House[s32_I - 1][2]) + ars32_Cost[0];
ars32_House[s32_I][1] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][2]) + ars32_Cost[1];
ars32_House[s32_I][2] = min(ars32_House[s32_I - 1][0], ars32_House[s32_I - 1][1]) + ars32_Cost[2];
}
cout << min(ars32_House[s32_N][0], min(ars32_House[s32_N][1], ars32_House[s32_N][2])) << endl;
return 0;
}
728x90
반응형
'백준' 카테고리의 다른 글
[ DP - 17626 ] Four Squares (0) | 2024.04.02 |
---|---|
[ DP - 2579 ] 계단 오르기 (0) | 2024.03.31 |
[ DP - 1003 ] 피보나치 함수 (0) | 2024.03.30 |
[ DP - 9095 ] 1, 2, 3 더하기 (1) | 2024.03.29 |
[ DP - 1463 ] 1로 만들기(C++) (0) | 2024.03.25 |