백준 BOJ 1149 - RGB거리

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

1149번: RGB거리

배열을 어떻게 만들어야 할지 고민했던 문제.

dp배열을 만든 뒤로는 그냥 무난하게 풀어냈다.

#include <stdio.h>

int dp[1001][3] = {0};
int min(int a, int b){ return a>b?b:a; }
int index(int k){ if(k==3){return 0;} if(k==-1){return 2;} return k; }
int main(){
	int n,tmp,value=1234567;
	
	scanf("%d", &n);
	for(int i=0; i<n; i++) for(int j=0; j<3; j++) scanf("%d", &dp[i][j]);
	
	for(int i=0; i<n; i++){
		for(int j=0; j<3; j++){
			dp[i+1][j] += min(dp[i][index(j+1)], dp[i][index(j-1)]);
		}
	}
	
	for(int i=0; i<3; i++) value = min(value, dp[n][i]);
	printf("%d", value);
	return 0;
}

min함수는 단순히 둘 중 더 작은 값을 반환하는 함수이고,

index함수는 배열 밖에 접근하는 세그멘테이션 폴트가 일어나지 않도록

범위밖일때 수정해주는 함수이다.

​

변수 선언해주고

입력받고

제일 중요한 부분은

for(int i=0; i<n; i++){
	for(int j=0; j<3; j++){
		dp[i+1][j] += min(dp[i][index(j+1)], dp[i][index(j-1)]);
	}
}

이 부분이 되겠다.

이중 포문을 통해 dp배열을 전부 탐색해준다.

같은 색을 고르면 안되기 때문에, j 값이 하나 있다면 index(j-1)과 index(j+1)번 인덱스에 접근할 수 있을것이다.

따라서 둘의 숫자를 비교해서, 더 작은 값을 선택해 dp배열에 넣어준다.

순서를 저장하지 않기때문에, 어떤 순서로 무엇을 저장했는지는 구할 필요가 없고,

단순히 dp[i+1][j] 가 가질 수 있는 가장 작은 값만을 구해내면 되기 때문에 이렇게 작성했다.

​

이걸 반복하면 결과적으로 dp[n]에 값이 세개 저장될 것이고,

이 세개 중 가장 작은 값을 출력하면 된다.

for(int i=0; i<3; i++) value = min(value, dp[n][i]);
printf("%d", value);

 

DP 많이많이 풀어가서 국민대 본선 잘봤으면 좋겠다 ㅎㅎ

​