백준 1149 (DP)

1149번: RGB거리

과정

• 음.. 그니까 내집 기준 앞번호, 뒷번호랑 집의 색까리 같으면 안된다.
• 그리고 색칠하는 비용이 모두 다르고, 최소값을 구하라고 하니까, DP와 min을 사용해서 코드를 짜볼것이다.
• 고민을 가장 많이 한 부분은 단순 최소값만 생각할게 아니라, 색의 종류도 함께 고민을 해야한다는 점이었다.
  key:value로 넣을 것인지, 아니면 그냥 RGB순서로 인덱스로 구분할 것인지 고민했다.
  : 이 부분은 코드를 짜다보니, 어차피 DP라는 특성상 현재는 R일지라도 G가 될수도 있고, 그렇게 색이 변할지 말지는 결국은 RGB값을 죄다 찾아봐야하기 때문에 굳이 색의 종류를 저장해야하나? 싶었다. 
• 그냥, 2번째집부터 앞뒤 집의 RGB일 때를 죄다 구해보기로 했다. 어차피 나에게는 min 함수가 있으니까!

코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int HouseNum = 0;   // 집의 수

int answer = 0;     // 모든 집을 색칠하는 최소 비용

vector<vector<int>> RGBCost (2, vector<int>(3, 0));     // 색칠하는 비용(총 집의 개수, RGB 비용)

vector<vector<int>> DP (2, vector<int>(3, 0));          // index번째 집기준 최소값을 저장

int main()

{

    cin >> HouseNum;

    RGBCost.resize(HouseNum+1, vector<int>(3, 0));

    DP.resize(HouseNum+1, vector<int>(3, 0));

    for (int i = 1; i < HouseNum+1; i++)

    {

        cin >> RGBCost[i][0] >> RGBCost[i][1] >> RGBCost[i][2];

    }

    // 첫번째 집 최소비용 설정

    DP[1][0] = RGBCost[1][0];   // 빨간집

    DP[1][1] = RGBCost[1][1];   // 초록집

    DP[1][2] = RGBCost[1][2];   // 파랑집

    for (int i = 2; i < HouseNum+1; i++)

    {

        for (int j = 0; j < 3; j++) // i번째 집의 색깔 j

        {

            if (j == 0)

                DP[i][0] = RGBCost[i][j] + min(DP[i-1][1], DP[i-1][2]);

            else if(j == 1)

                DP[i][1] = RGBCost[i][j] + min(DP[i-1][0], DP[i-1][2]);

            else

                DP[i][2] = RGBCost[i][j] + min(DP[i-1][0], DP[i-1][1]);

        }

    }

    answer = min({DP[HouseNum][0], DP[HouseNum][1], DP[HouseNum][2]});

    cout << answer;

    return 0;

}

 

처음에는 이렇게 작성하긴 했는데.. 뭔가 for문을 저렇게 한번 더 써야하나 싶었다. 코드를 더 줄여보니,

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int HouseNum = 0;   // 집의 수

int answer = 0;     // 모든 집을 색칠하는 최소 비용

vector<vector<int>> RGBCost (2, vector<int>(3, 0));     // 색칠하는 비용(총 집의 개수, RGB 비용)

vector<vector<int>> DP (2, vector<int>(3, 0));          // index번째 집기준 최소값을 저장

int main()

{

    cin >> HouseNum;

    RGBCost.resize(HouseNum+1, vector<int>(3, 0));

    DP.resize(HouseNum+1, vector<int>(3, 0));

    for (int i = 1; i < HouseNum+1; i++)

    {

        cin >> RGBCost[i][0] >> RGBCost[i][1] >> RGBCost[i][2];

        DP[i][0] = RGBCost[i][0] + min(DP[i-1][1], DP[i-1][2]);

        DP[i][1] = RGBCost[i][1] + min(DP[i-1][0], DP[i-1][2]);

        DP[i][2] = RGBCost[i][2] + min(DP[i-1][0], DP[i-1][1]);

    }

    answer = min({DP[HouseNum][0], DP[HouseNum][1], DP[HouseNum][2]});

    cout << answer;

    return 0;

}

 

이렇게도 가능했다.

(1번집의 경우 0번집이 없지만, 벡터를 초기화할 때 기본적으로 죄다 0을 넣었기때문에 0으로 계산되어 들어간다.)