[백준 1149] RGB거리

RGB거리

문제설명

집에 빨강,초록,파랑으로 색을 칠하려 한다. 위의 사진에서 규칙을 확인하고 모든 집을 칠하는 비용의 최솟값을 출력하라.

알고리즘

1. 값을 각각 입력받고 dp의 값을 저장할 부분인 result에 초기 값을 입력 받은 값으로 설정해준다.
2. 반복문으로 나머지 부분을 각 색깔에 맞춰서 해당 색은 사용하지 않은 가장 작은 전 값에 현재 색을 더해준다.
3. N만큼 진행하고 가장 끝 행에 값들 중 가장 작은 값을 출력시킨다.

---

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAX 1001
using namespace std;
int N; 
int graph[MAX][3];
int result[MAX][3];//결과 값을 저장하기 위한 배열

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 3; j++)
            cin >> graph[i][j];
    }
    //첫 값 설정 
    result[0][0] = graph[0][0];
    result[0][1] = graph[0][1];
    result[0][2] = graph[0][2];

    for (int i = 1; i < N; i++)//dp 업데이트 
    {
        result[i][0] += min(result[i-1][1], result[i-1][2]) + graph[i][0];//빨강은 파랑 초록중에 작은 값을 골라 빨간색 값을 더해준다
        result[i][1] += min(result[i-1][0], result[i-1][2]) + graph[i][1];//파랑은 빨강 초록중에 작은 값을 골라 파란색 값을 더해준다
        result[i][2] += min(result[i-1][0], result[i-1][1]) + graph[i][2];//초록은 파랑 빨강중에 작은 값을 골라 초록색 값을 더해준다
    }


    int ans = min(result[N - 1][2], min(result[N - 1][0], result[N - 1][1]));//가장 끝 행중에 결과 중 가장 작은 값이 총 비용
    cout << ans;

    return 0;
}

고찰

이번 문제는 dp문제로 처음에는 막막한 편이 있었다. 최소값을 구해서 각각 업데이트 시켜서 답을 구하면 되는데,
처음에는 일차원 배열에 저장해서 구하려했다.

하지만 틀렸습니다가 떠서 검색해서 답을 저장하는 방식을 참고했다.

2차원 배열 형태로 입력받은 값과 같은 크기의 배열을 만들고 이 전의 색을 반영해서 그 색은 제외한 가장 작은 값을 구하고 현재 색을 칠하는 방식으로 알고리즘을 구성했다.

마지막엔 가장 끝행에서 제일 작은 값을 출력하면 답이 된다.