1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
해결 방법
이 문제의 시간 제한은 0.5초로 짧다.
중첩 반복문을 이용한 브루트 포스의 방법으론 통과할 수 없다는 의미이다.
dp로 문제를 해결하기 위해선 점화식, 즉 규칙을 찾아내야한다.
입력 값으로 행은 2 ~ 1000까지 최대 999개의 행이 주어지고,
열은 0, 1, 2로 총 3개의 열이 주어진다.
이 문제의 핵심은 행의 최소 값을 다음 행의 원소와 더하되 열이 같지 않은 원소에 더해야 한다는 것이다.
입력 값이 저장된 배열을 house라고 했을 때
이를 점화식으로 구현하면
dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + house[n][0]
dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + house[n][1]
dp[n][2] = min(dp[n-1][0], dp[n-1][1]) + house[n][2]
가 된다.
위 과정을 모든 행에 대해서 반복하면 마지막 행에는 각 열에서의 최소값들이 담겨 있다.
이 값들 중에서 가장 작은 값을 출력하면 정답.
해결 과정
점화식을 코드로 구현하고 마지막 행에서 최소값을 찾는 코드를 추가한다.
최종 코드는
#include <iostream>
using namespace std;
int min(int a, int b){
return a < b ? a : b;
}
int main(){
int n, a, b, c, result;
int house[999][3];
int dp[999][3];
cin >> n;
for(int i = 0; i < n; i++){
cin >> a >> b >> c;
house[i][0] = a;
house[i][1] = b;
house[i][2] = c;
}
dp[0][0] = house[0][0];
dp[0][1] = house[0][1];
dp[0][2] = house[0][2];
for(int i = 1; i < n; i++){
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house[i][0];
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house[i][1];
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house[i][2];
}
result = dp[n-1][0];
for(int i = 1; i < 3; i++){
if (result > dp[n-1][i]){
result = dp[n-1][i];
}
}
cout << result;
return 0;
}
min 함수는 더 작은 값을 return 해주는 함수이다.
'✍️ 코테 준비 > Dynamic Programming' 카테고리의 다른 글
[동적 계획법 1] [C++] 2579번. 계단 오르기 (0) | 2021.01.14 |
---|---|
[동적 계획법 1] [C++] 1932번. 정수 삼각형 (0) | 2021.01.13 |
[동적 계획법 1] [C++] 1149번. RGB 거리 (0) | 2021.01.13 |
[동적 계획법 1] [C++] 9461번. 파도반 수열 (0) | 2021.01.13 |
[동적 계획법 1] [Python] 1904번. 01타일 (0) | 2021.01.12 |
[동적 계획법 1] [Python] 9184번. 신나는 함수 실행 (0) | 2021.01.12 |