[Baekjoon Online Judge] 백준 1149번 RGB거리(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1149번 RGB거리

(C++, Python)

(글쓴날 : 2020.04.13)

 

---

* Baekjoon Online Judge, 백준 1149번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1149번 RGB거리

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1149

1149번: RGB거리

---

2) 풀이 과정

N개의 집이 주어지고 해당 집들마다 비용이 다른 빨강, 초록, 파랑 중 하나의 색으로 칠할 때 규칙에 만족하여 모든 집을 칠하는 최소 비용을 구하는 문제입니다.

주어진 규칙은 복잡해 보이지만 결국, 현재 집에 칠할 색이 이전 집과 겹치지 않으면 되는 것으로 귀결됩니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과, Python을 사용했습니다.

첫 번째 집을 빨강, 초록, 파랑으로 칠하는 3가지 경우의 비용을 memoization할 costs라는 2차원 테이블을 만든 후, 다음 집부터 각 색깔들을 칠할 시, 현재 칠할 색을 제외한 색깔로 이전 집을 칠한 최소 비용을 더해, costs에 총비용을 계속 누적해가며, 최종적으로 마지막 집을 칠한 비용들 중 최소비용을 출력하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int N = 0;
    cin >> N;
 
    vector<int[3]> prices(N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> prices[i][j];
        }
    }
 
    vector<int[3]> costs(N);
    int candidatePrice = 0;
 
    for (int i = 0; i < N; i++)
    {
        if (i == 0)
        {
            costs[i][0] = prices[i][0];
            costs[i][1] = prices[i][1];
            costs[i][2] = prices[i][2];
            continue;
        }
        for (int j = 0; j < 3; j++)
        {
            candidatePrice = 1000001;
 
            for (int k = 0; k < 3; k++)
            {
                if (!(j == k))
                {
                    if (candidatePrice > costs[i - 1][k])
                        candidatePrice = costs[i - 1][k];
                }
            }
 
            costs[i][j] = prices[i][j] + candidatePrice;
        }
    }
 
    cout << *min_element(costs[N - 1], costs[N - 1] + 3);
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
prices = [list(map(int, input().split())) for _ in range(N)]
costs = [[0] * 3 for _ in range(N)]
 
for i in range(N):
    if i == 0:
        costs[i][0] = prices[i][0]
        costs[i][1] = prices[i][1]
        costs[i][2] = prices[i][2]
        continue
    
    for j in range(3):
        candidatePrice = 1000001
 
        for k in range(3):
            if not j == k:
                if candidatePrice > costs[i - 1][k]:
                    candidatePrice = costs[i - 1][k]
            
        costs[i][j] = prices[i][j] + candidatePrice
    
print(min(costs[-1]))

---