다이나믹 프로그래밍 문제입니다.
파란색, 빨간색, 초록색이 존재하고
이웃하는 집에는 같은색을 칠할 수 없습니다.
각각 집마다 페인트의 가격이 다르므로
최소의 돈을 써서 페인트를 칠하는 문제입니다.
memo[1000][3] 배열에 각각의 집마다의 페인트 가격을 입력합니다.
현재 위치에서의 색과 전의 이웃에서의 색이 같으면 찾을 필요없기에
다른 색인 곳만 찾아서 적은 값인 곳을 현재 값과 더해주면서 값을 구합니다.
memo[i][0] += min(memo[i - 1][1], memo[i - 1][2]);
memo[i][1] += min(memo[i - 1][0], memo[i - 1][2]);
memo[i][2] += min(memo[i - 1][0], memo[i - 1][1]);
이렇게 나타낼 수 있습니다.
#include
#include
using namespace std;
int main(int argc, char *argv[])
{
int memo[1000][3];
int n;
int minMemo = 987654321;
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
memo[i][j] = 0;
cin >> memo[i][j];
}
}
for (int i = 1; i < n; ++i) {
memo[i][0] += min(memo[i - 1][1], memo[i - 1][2]);
memo[i][1] += min(memo[i - 1][0], memo[i - 1][2]);
memo[i][2] += min(memo[i - 1][0], memo[i - 1][1]);
}
for (int i = 0; i < 3; ++i) {
if (minMemo > memo[n - 1][i]) {
minMemo = memo[n - 1][i];
}
}
cout << minMemo;
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 1932번 정수 삼각형 (0) | 2019.05.17 |
---|---|
[C++] 백준 2193번 이친수 (0) | 2019.05.17 |
[C++] 백준 2447번 별 찍기 - 10 (4) | 2019.05.07 |
[C++] 백준 1669번 멍멍이 쓰다듬기 (0) | 2019.05.05 |
[C++] 백준 1947번 선물 전달 (0) | 2019.05.05 |