문제 출처 : www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
알고리즘 분류
풀이
규칙을 찾아 dp를 활용하는 문제다.
N이 최대 1000이고 집마다 세 가지 색상으로 칠할 수 있으므로,
각 집마다 세 가지 색상을 칠했을 때의 최소비용을 저장할 배열 house[1001][3]을 선언한다.
n 번째 집에 red, green, blue 각각의 색을 칠했을 때, 최솟값을 구하면 된다.
n 번째 집에 red를 칠할 경우, n-1 번째 집은 green이나 blue를 칠할 수 있는데, green이나 blue중
비용이 적게 드는 색상의 비용과, n 번째 집에 red색상을 칠하는 비용을 더하면 이것이
n 번째 집에 red를 칠했을 때의 최소비용이다.
n 번째 집에 green이나 blue 색을 칠했을 때도 마찬가지다.
코드
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int house[1001][3];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
int cost[3];
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) {
cin >> cost[j];
}
house[i][0] = min(house[i - 1][1], house[i - 1][2]) + cost[0];
house[i][1] = min(house[i - 1][0], house[i - 1][2]) + cost[1];
house[i][2] = min(house[i - 1][0], house[i - 1][1]) + cost[2];
}
cout << min(house[n][0], min(house[n][1],house[n][2]));
}
'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
백준 2579 계단 오르기 c++ (0) | 2021.04.09 |
---|---|
백준 1932 정수 삼각형 c++ (0) | 2021.04.09 |
백준 9461 파도반 수열 c++ (0) | 2021.04.08 |
백준 1904 01타일 c++ (0) | 2021.04.08 |
백준 2748 피보나치 수 2 c++ (0) | 2021.04.07 |
댓글