끄적끄적 코딩
article thumbnail
Published 2019. 5. 9. 03:24
[C++] 백준 1149번 RGB거리 알고리즘

다이나믹 프로그래밍 문제입니다.

파란색, 빨간색, 초록색이 존재하고

이웃하는 집에는 같은색을 칠할 수 없습니다.

각각 집마다 페인트의 가격이 다르므로

최소의 돈을 써서 페인트를 칠하는 문제입니다.

 

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; 
}

검색 태그