[백준] 1149 - RGB거리 (C++)

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

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 문제다.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• i(2≤i≤N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 2 ≤ N ≤ 1,000
• 1 ≤ 집을 칠하는 비용 ≤ 1,000

 

j번째 집을 i로 칠하고 난 뒤에 든 모든 비용의 최솟값을 저장할 dp[i][j] 배열을 선언해야 한다. 색을 칠할 때, 색을 칠하려는 집의 이전 집이 무슨 색으로 칠해졌는지에 따라 칠할 수 있는 색이 2개로 정해진다. 예를 들어 빨간색을 0, 초록색을 1, 파란색을 2로 보면, i번째 집을 0으로 칠하려면 i-1번째 집은 1 또는 2로 칠해져 있어야 한다.

 

아래 코드처럼 짜도 상관없지만, 이렇게 지금의 상태가 이전의 상태에만 영향을 받는 경우엔 dp 배열을 N만큼 선언하지 않고 0 또는 1의 값만 가질 수 있게 선언해 메모리를 아낄 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;

int n,dp[3][1001],a,b,c;

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

    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a >> b >> c;
        dp[0][i] = a + min(dp[1][i-1],dp[2][i-1]);
        dp[1][i] = b + min(dp[0][i-1],dp[2][i-1]);
        dp[2][i] = c + min(dp[0][i-1],dp[1][i-1]);

    }

    cout << min({dp[0][n],dp[1][n],dp[2][n]});
}

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N 입력받기
2. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용을 입력받고 dp 배열을 갱신하면서 진행하기
   1. dp[i][j] → j번째 집을 i(0: R, 1: G, 2:B)로 칠한 누적 비용들 중 최솟값을 저장하는 배열
3. 마지막 집을 빨강, 초록, 파랑으로 칠하고 난 비용을 dp 배열에 더하고 그중 가장 작은 값 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1회차

• 런타임 에러 (OutOfBounds) → 배열을 선언할 때 범위를 1 작게 지정함

 

---

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,dp[3][2],a,b,c;

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

    bool tog;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a >> b >> c;
        tog = (i%2==1 ? true : false);
        dp[0][tog] = a + min(dp[1][!tog],dp[2][!tog]);
        dp[1][tog] = b + min(dp[0][!tog],dp[2][!tog]);
        dp[2][tog] = c + min(dp[0][!tog],dp[1][!tog]);

    }

    cout << min({dp[0][tog],dp[1][tog],dp[2][tog]});
}