백준 1145번 RGB거리 [성공]

https://www.acmicpc.net/problem/1149

1149번: RGB거리

2차원 배열로 푸는 다이나믹 프로그래밍 문제이다.

각 지점에 대해 앞배열의 정보를 이용해 푼다. -> 이미 계산된 결과를 이용

#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
	int num;
	cin>>num;
	vector<vector<int>> dp;
	vector<int> temp;
	for(int i=0;i<3;i++){
		temp.push_back(0);
	}
	dp.push_back(temp);
	temp.clear();
	int num_input;
	for(int i=1;i<=num;i++){
		for(int j=0;j<3;j++){
			cin>>num_input;
			if(j==0){
				temp.push_back(min(dp[i-1][1],dp[i-1][2]) + num_input);
			}else if(j==1){
				temp.push_back(min(dp[i-1][0],dp[i-1][2]) + num_input);
			}else if(j==2){
				temp.push_back(min(dp[i-1][0],dp[i-1][1]) + num_input);
			}
		}
		dp.push_back(temp);
		temp.clear();
	}
	
	
	cout<<min(min(dp[num][0],dp[num][1]),dp[num][2]);
	return 0;
}

 

중간에 불필요한 for문이 있지만 중간에 저장할 배열을 선언하지 않기 위해서 이 방식을 선택했다.

더 좋은 방법이 있겠지만 vector를 연습중이라 사용하였다.