백준 1149번 RGB거리 [C++] DP/예상되는 실수/접근방식/풀이법/코드

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

1149번: RGB거리

문제와 접근방식

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보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

조건

0.5초 128MB

접근방식

우선, 0.5초와 N이 1000이라는 사실으로, O(N^3)은 불가능하다는 사실을 인지하고, 브루트포스가 3^N이라는 것을 생각해보았을때, 브루트포스도 안되고, 그리디기법도 앞뒤가 연관이 있기때문에 불가능하므로 이 문제는 dP임을 인지해야한다.

 

문제풀이

각 집마다 칠하는 비용을 입력받아 2차원 배열에 넣고, 이 색깔로 칠하지 않는다라는 배열을 만들어내는게 핵심이다. 

i번째 집을 빨간색으로 칠하지 않는 최소한의 비용은 i-1이 노란색이 아니고 i가 노란색 or i-1이 파란색이 아니고 i가 파란색으로 칠하는 것 두가지로 계산하는게 핵심이다.

그렇게 쭉 dp로 계산하면 시간복잡도 O(N)으로 계산할 수 있다. 

 

코드

#include <stdio.h>
#include <algorithm>

using namespace std;
int N, answer;
int colormoney[1001][3]; //0은 빨강 1은 초록 2는 파랑색을 칠하는데 드는 가격
int answermoney[1001][3]; // 0은 빨강말고, 1은 초록말고, 2는 파랑말고
int main()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 2; j++) {
            scanf("%d", &colormoney[i][j]);
        }

    }
    answermoney[1][0] = min(colormoney[1][1], colormoney[1][2]);
    answermoney[1][1] = min(colormoney[1][0], colormoney[1][2]);
    answermoney[1][2] = min(colormoney[1][0], colormoney[1][1]);
    for (int i = 2; i <= N; i++) {
        answermoney[i][0] = min(answermoney[i - 1][1] + colormoney[i][1], answermoney[i - 1][2] + colormoney[i][2]);
        answermoney[i][1] = min(answermoney[i - 1][0] + colormoney[i][0], answermoney[i - 1][2] + colormoney[i][2]);
        answermoney[i][2] = min(answermoney[i - 1][0] + colormoney[i][0], answermoney[i - 1][1] + colormoney[i][1]);
    }
    answer = min(answermoney[N][0], answermoney[N][1]);
    answer = min(answer, answermoney[N][2]); //이 부분은 3개중 가장 작은 가격을 찾는방식. 
    printf("%d", answer);

}

스스로 풀었는데 막히는 자들을 위한 "실수하기 쉬운 부분"

1. min을 활용하지 않고, 조건문을 사용했을경우, 실수가 발생할 수 있다.

2. 첫번째 것부터 앞에것을 참조할경우 1부터 시작했을경우 논리적 오류가, 0부터 시작했을경우 에러가 뜬다. (-1 참조)

3. 시간 초과등이 발생한 경우, 본인의 시간복잡도가 O(N)이상이라면 알고리즘 자체를 잘못 생각한것.

4. 마지막 답을 낼때는 끝이 빨강이든, 노랑이든, 파랑이든 상관없다. 그것을 고려해서 코드를 짜자. 

 

이 문제에서 얻을 수 있는 내용

DP 기초, min사용법