[leetcode curated algo 170] 256. Paint house (C++)

256.  Paint House

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

• For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

 

한줄요약 :
집들을 3가지 색으로 색칠하려고 하는데,
앞서 칠했던 색을 바로 다시 쓸순없고, 색마다 cost가 다름, cost가 가장 적게 칠할때, 그 합은 ? 

 

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]
Output: 2

 

 

  IDEA : 

최소비용 문제이므로, DP를 떠올리는게 좋을것 같다. 

 

n번째 집에서 3가지 색을 각각 골랐을때,  n-1 회차에서 현재 고른 색깔과 다른 색 중 cost 가  가장 작은 값에

을 계속 구해 나가면 된다. 

 

n번째 집에서 3가지 색을 칠할때 cost를 각각 구해야 하므로, 

저장할 배열 구조는 N x 3 이 될 것이다. 

 

순서 

1) 0번 회차를 구한다. 0번회차를 구해 놓으면, 이를 토대로 1번 회차를 구할 수 있다.

2) 1번 회차를 구할땐, 0번 회차 중에 현재 선택한 컬러를 제외하고, 가장 작은 값을 가져온다. 

회차	0	1	2	3	4	5
빨강	17	2+16=18	14+7=>21
파랑	2	17+16=31	3+7=>10
초록	17	2+5=7	19+18=>37

 

 code 

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        
        int n = costs.size();    
        vector<vector<int>> box(n, vector<int>(3,0));  // 이차원 벡터 선언
        
        for(int i=0; i< costs[0].size(); i++ )
            box[0][i] = costs[0][i];
        
        for(int i=1; i <n; i++){            
            box[i][0] = min(box[i-1][1], box[i-1][2]) + costs[i][0];
            box[i][1] = min(box[i-1][0], box[i-1][2]) + costs[i][1];
            box[i][2] = min(box[i-1][0], box[i-1][1]) + costs[i][2];
        }
            
        return min(min(box[n-1][0],box[n-1][1]), box[n-1][2]);        
        
    }
};