코딩 챌린지 7일차 : 1149번 RGB거리(S1)

1149 : RGB거리 - 문제 링크

1. 문제 탐색하기

입력

n 집의 수
houses[3][n] 집을 RGB로 칠하는 데에 드는 비용 정보

구하고자 하는 것

이웃집과 색이 겹치지 않게 집을 칠하는 비용의 최솟값

알고리즘 설계

6일차의 자원 캐기 문제와 비슷하게 접근
n번째 집을 최소의 비용으로 칠하기 위해서는
n - 1번째 집까지 최소 비용을 들여 칠하는 방법에
n - 1번째 집과 다른 색 중 더 작은 비용이 드는 색으로 칠하면 된다.

예제 입력 1을 참고

우선 A[1]을 1번 집의 색상별 비용인 (26, 40, 83)으로 두고, A[2]를 구해보자.
R인 49로 칠하는 방법은 (40, 49), (83, 49)로 합이 더 적은 (40, 49)를,
G인 60로 칠하는 방법은 (26, 60), (83, 60)로 합이 더 적은 (26, 60)을,
B인 57로 칠하는 방법은 (26, 57), (40, 57)로 합이 더 적은 (26, 57)을 택한다.
그럼 A[2]는 (89, 86, 83)이 된다.

A[2]를 가지고 위의 작업을 수행하여 A[3]를 구한다.
이전 항은 2번 집의 색상별 비용이 아니라,
2번 집을 해당 색상으로 칠했을 때의 가능한 비용합의 최솟값이 이전 항이 된다.
계산하면 A[3]은 (96, 172, 185)이다.
여기서 결과값은 세 가지 중 가장 작은 값인 96이다.

A[n]은 n - 1번째 집을 각 색상으로 칠했을 때의 총 최소 비용인 A[n - 1]
+ n번째 집을 칠할 수 있는 두 가지 중 더 작은 값으로 정의할 수 있다.

시간복잡도

2 ~ n번째 집까지, 3가지 색상에 대해 연산 -> 3(n - 1) -> $O(n)$
2 $\leq$ n $\leq$ 1,000 이므로 약 3,000번의 연산 수행 => 통과 가능

2. 코드 설계하기

1. input 받기
2. houses[i - 1]에 houses[i]를 칠할 수 있는 방법 중 더 작은 값을 더한다.
• 세 가지 색상에 대해 모두 수행
• houses[i]의 값을 결과값으로 바꾸어 줌
3. houses[n-1]의 최솟값 출력

3. 시도 회차 수정 사항

1회차) 성⭐공

4. 정답 코드

import sys
input = sys.stdin.readline

# input 받기
n = int(input())
houses = [list(map(int, input().split())) for _ in range(n)]

# DP
for i in range(1, n):
    for j in range(3):
        houses[i][j] += min(houses[i - 1][(j + 1) % 3], houses[i - 1][(j + 2) % 3])

print(min(houses[n - 1]))

어제 자원 캐기에서 고생하고 나니까 비교적 빨리 솔루션을 찾을 수 있었다. DP에 감도 좀 오는 것 같고?! 요즘 바빠서 그런가 슬슬 해이해지는 것 같은데... 정신🍒

5. 해설지 참고 후

• 한 상태를 만드는데 여러 상태가 활용된다면 2차원 DP사용
• DP배열을 만들어준 게 공간은 차지해도 더 DP스러운 풀이같기는 하다.