[백준] 1149번: RGB거리 (C언어) - 배열 사용 안 하는 풀이법

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

1149번: RGB거리

난이도: solved.ac 실버 1
 
 
예제 1을 가지고 설명해보겠다
예제 1의 input을 표로 나타내면 아래와 같다
 

	RED	GREEN	BLUE
1번	26	40	83
2번	49	60	57
3번	13	89	99

 
일단 dp 문제답게 n 번째까지의 합을 구할 때 n - 1 번째까지의 합을 이용할 건데,
내 풀이에서 핵심은 Red, Green, Blue를 일단 모두 칠해보고
그때의 각 최솟값을 구하는 것이다
여기서 n - 1 번째 자리에 Red를 칠했을 때의 최솟값을 r, Green을 칠했을 때의 최솟값을 g, Blue를 칠했을 때의 최솟값을 b라고 하겠다
 
단계별로 차근차근 풀기 위해 3번 행을 없는 셈 치고 2번 행까지만 보자
 
2번 자리에 Red를 칠한다고 해보자
이때 최솟값은 어떻게 될까?
1번 자리에서 Red는 못 칠하므로 Green와 Blue 중 더 싼 걸 골라 49(= 2번에서의 Red값)를 더한 값일 것이다
 
그럼 2번 자리에 Green을 칠한다고 하면 최솟값은 얼마일까?
1번 자리에서 Green을 뺀 Red와 Blue 중 더 싼 것인 Red(= 26)에 60을 더한 값일 것이다
 
Blue를 칠한다고 가정했을 때의 최솟값은
1번에서 Red와 Green 중 더 싼값인 26에 57을 더한 값일 것이다
 
이를 정리하면 다음과 같다
 
2번 자리가
Red일 때의 최솟값: 40 + 49= 89  (3번 입장에서 r)
Green일 때의 최솟값: 26 + 60= 86  (3번 입장에서 g)
Blue일 때의 최솟값: 26 + 57= 83  (3번 입장에서 b)
 
3번 자리에 Red, Green, Blue를 칠할 때 각각의 최솟값은 어떻게 구할까?
 
3번 자리에 Red를 칠한다고 하면,
2번 자리에서 Green을 칠했을 때의 최솟값(g)과 Blue를 칠했을 때의 최솟값(b) 중 더 작은 값에 3번 자리의 Red값을 더해주면 된다
위에서 g = 86이었고 b = 83이었으니,
g와 b 중 더 작은 b에 13을 더한 96이 된다
 
3번 자리에 Green을 칠했을 때는
2번 자리에서 Red를 칠했을 때의 최솟값(r)과 Blue를 칠했을 때의 최솟값(b) 중 더 작은 값인 b에 3번 자리의 Green값(= 89)을 더해주면 된다
 
3번 자리에 Blue를 칠했을 때는 위와 똑같은 방식으로
2번 자리에서 Red를 칠했을 때의 최솟값(r)과 Green을 칠했을 때의 최솟값(g) 중 작은 값인 g에 Blue의 값(= 99)을 더해주면 된다
 
이를 정리하면
 
3번 자리가
Red일 때의 최솟값: g(= 86)과 b(= 83) 중 더 작은 것 + 13 = 96
Green일 때의 최솟값: r(= 89)과 b(= 83) 중 더 작은 것 + 89 = 172
Blue일 때의 최솟값: r(= 89)과 g(= 86) 중 더 작은 것 + 99 = 185
가 된다
 
따라서 최솟값은 96이 된다
 
이 과정을 코드로 나타내면 아래와 같다
 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    int N, i, R, G, B, min;
    int r = 0, g = 0, b = 0;	// r, g, b: n-1번째까지의 합
    int tmp_r, tmp_g, tmp_b;

    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        // 각 집의 RGB 비용 입력받기
        scanf("%d %d %d", &R, &G, &B);

        // 이전 집의 색상 중 겹치지 않는 색상으로 칠할 경우의 비용 계산
        tmp_r = (g < b ? g : b) + R; // 이전 집을 초록 또는 파랑으로 칠했을 때 더 작은 비용에 현재 집을 빨강으로 칠하는 경우
        tmp_g = (r < b ? r : b) + G; // 이전 집을 빨강 또는 파랑으로 칠했을 때 더 작은 비용에 현재 집을 초록으로 칠하는 경우
        tmp_b = (r < g ? r : g) + B; // 이전 집을 빨강 또는 초록으로 칠했을 때 더 작은 비용에 현재 집을 파랑으로 칠하는 경우

        // 계산된 비용을 이전 집의 색상 변수에 할당하여 다음 집의 비용 계산에 사용
        r = tmp_r;
        g = tmp_g;
        b = tmp_b;
    }

    // 마지막 집까지 모두 칠했을 때의 최소 비용 계산
    if (r < g) min = r;
    else min = g;
    if (b < min) min = b;

    // 최소 비용 출력
    printf("%d", min);

    return 0;
}