[백준] RGB거리 (1149번)

난이도 : Silver1
Link : https://www.acmicpc.net/problem/1149
Tag : 다이나믹 프로그래밍
풀이일자 : 2024년 9월 15일

📌 문제 탐색하기

N: 집의 개수

조건: 집을 칠할 때 연속되게 칠하면 안된다.
따라서 R 칠했을 때 G,B를 G를 칠했을 때 R,B를 B를 칠했을 때 R,G를 칠할 수 있다.

가능한 시간복잡도

탐색할 자원의 크기는 N이므로 탐색할 수 있는 시간복잡도는 O(n)으로 생각 할 수 있다.

📌 문제 접근 방법

DP를 이용하여 RGB색을 칠할때 최솟값을 집의 좌표마다 저장한다면 해결할 수 있을것이다.

grid 배열에 각 집의 칠하는 비용을 저장하고
dp 배열에 색상별 비용을 저장할 것이다.

dp[i][0] R
dp[i][1] G
dp[i][2] B
이런식으로 각 색별로 값을 누적해 나가면 최소값을 구할 수 있다.

📌 코드 설계하기

1. n을 입력받는다.

2. grid를 입력받는다.

3. 첫번째 dp 배열을 초기화 한다.

   dp[0][0] = grid[0][0]
   dp[0][1] = grid[0][1]
   dp[0][2] = grid[0][2]

4. 빨강, 초록, 파랑을 칠할때의 누적값을 저장한다. (이때 각 색을 칠할때 가격이 낮은것을 선택한다.)

   for i in range(1,n):
   dp[i][0] = min(dp[i-1][1] + grid[i][0], dp[i-1][2] + grid[i][0]) #빨강을 칠할때
   dp[i][1] = min(dp[i-1][0] + grid[i][1], dp[i-1][2] + grid[i][1]) #초록을 칠할때
   dp[i][2] = min(dp[i-1][0] + grid[i][2], dp[i-1][1] + grid[i][2]) #파랑을 칠할때

5. 최종적으로 칠한 색중 최솟값인 것을 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())
grid = [list(map(int,input().split())) for i in range(n)]

dp = [[0]* 3 for _ in range(n)]

# dp[i][0] R
# dp[i][1] G
# dp[i][2] B
dp[0][0] = grid[0][0]
dp[0][1] = grid[0][1]
dp[0][2] = grid[0][2]

for i in range(1,n):
    dp[i][0] = min(dp[i-1][1] + grid[i][0], dp[i-1][2] + grid[i][0]) #빨강을 칠할때
    dp[i][1] = min(dp[i-1][0] + grid[i][1], dp[i-1][2] + grid[i][1]) #초록을 칠할때
    dp[i][2] = min(dp[i-1][0] + grid[i][2], dp[i-1][1] + grid[i][2]) #파랑을 칠할때

print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))