[백준 1149] RGB거리 (DP)

🌰문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

🌰입출력 예시

 

예제 입력 1 

3
26 40 83
49 60 57
13 89 99

 

 

예제 출력 1 

96

 

---

 

예제 입력 2 

3
1 100 100
100 1 100
100 100 1

 

 

예제 출력 2 

3

 

---

 

예제 입력 3 

3
1 100 100
100 100 100
1 100 100

 

예제 출력 3 

102

 

---

 

예제 입력 4 

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

 

예제 출력 4 

208

 

---

 

 

예제 입력 5 

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

 

 

예제 출력 5 

253

 

---

🌰문제 풀이

 

처음 생각한 풀이 방식

처음에는 첫 번째 집을 초기화 해놓고, 두 번째 집부터는 초기화된 DP테이블을 이용하여, 최소 비용을 찾아가려고 했다. 

 

그러나, 문제를 풀 수록 딜레마에 빠졌다.

우선, 위 -> 아래로 가면, 당장 눈 앞에 보이는 최소 비용이, 최종적으로 최소 비용를 만드는 선택이 아닐 수 있었다.

 

예를 들어보자

3
26 40 83
49 20 21
13 1 100

 

위와 같이 있을 때, 첫 번째 줄의 26입장에서 두 번째 집의 G(20), B(21) 중에서 선택할 수 있다.

이 때, G(20)을 선택하는 것이 당장은 좋은 선택인 듯 하다.

 

하지만, 그렇게 되면, 세 번째 줄에서 G(1)을 선택하지 못하게 된다!

따라서, B(21)을 선택하는 것이 최종적으로 봤을 때는 더 합리적인 선택인 것(G(1)을 선택할 수 있으니)

 

 

위->아래로 가는 방식은 다음 줄에서 최소비용은 고려할 수 있지만, 그 선택이 다다음 줄에 미치는 영향은 고려하지 못한다는 문제가 있었다.

 

최종적으로 생각해낸 풀이 방식

맨 아래 집에서부터 위로 올라가면서 최적의 비용을 계산하는 방식을 생각했다. 각 집에서 선택할 수 있는 최적의 색은 다음 집에서 선택한 색을 기준으로 최소 비용을 가지는 색인 것.

 

무슨 말이냐고?

코드를 분해해서 살펴보자

 

 

🌰코드 분석

1. DP 테이블 초기화

 

먼저, 주어진 입력에 따라 각 집을 색칠하는 비용을 2차원 리스트 cost_list에 저장한다.

이후 동적 계획법을 위한 dp 테이블을 생성한다

 dp[i][j]는 i번째 집을 j번째 색으로 칠했을 때의 최소 비용을 저장하는 리스트이다

# 집의 개수 입력
N = int(input())

# 각 집을 칠하는 비용 입력 받기
cost_list = []
for i in range(N):
    cost_list.append(list(map(int, input().split())))

# 동적 계획법을 위한 dp 테이블 초기화
dp = [[0, 0, 0] for _ in range(N)]

 

 

2. 맨 아래 집 초기화

 

마지막 집은 비교할 다음 집이 없으므로 그 집의 각 색깔로 칠하는 비용을 그대로 dp 테이블에 기록하자

# 마지막 집 초기화: 각 색깔로 칠하는 비용 그대로 저장
dp[-1][0] = cost_list[-1][0]  # 마지막 집을 빨강으로 칠하는 비용
dp[-1][1] = cost_list[-1][1]  # 마지막 집을 초록으로 칠하는 비용
dp[-1][2] = cost_list[-1][2]  # 마지막 집을 파랑으로 칠하는 비용

 

3. 맨 아래 집부터 위로 올라가며 최소 비용 계산

 

N-2번째 집부터 첫 번째 집까지, 각 집에서 선택할 수 있는 색깔을 고려해 그 집을 색칠하는 비용을 계산한다.

 

⭐ dp[i][j]는 i번째 집을 j번째 색으로 칠했을 때, 바로 아래 집에서 선택할 수 있는 다른 두 가지 색의 비용 중 더 적은 값을 더하여 업데이트되도록 한다

 

# 맨 아래 집에서부터 첫 번째 집까지 거꾸로 올라가며 DP 테이블 채우기
for i in range(N-2, -1, -1):
    for j in range(3):
        if j == 0:
            # 첫 번째 색(빨강)을 선택한 경우: 다음 집에서 초록이나 파랑을 선택한 최소 비용을 더함
            dp[i][j] = cost_list[i][j] + min(dp[i+1][1], dp[i+1][2])
        elif j == 1:
            # 두 번째 색(초록)을 선택한 경우: 다음 집에서 빨강이나 파랑을 선택한 최소 비용을 더함
            dp[i][j] = cost_list[i][j] + min(dp[i+1][0], dp[i+1][2])
        else:
            # 세 번째 색(파랑)을 선택한 경우: 다음 집에서 빨강이나 초록을 선택한 최소 비용을 더함
            dp[i][j] = cost_list[i][j] + min(dp[i+1][0], dp[i+1][1])

 

🌰최종 코드

#앞에서 부터 가면,당장 눈 앞에 보이는 최솟값이 찐 최소비용의 경로가 아닐 수 있어
#마지막->위로 가보자.

N = int(input())
cost_list = []
for i in range(N):
    cost_list.append(list(map(int,input().split())))


dp = [[0,0,0] for _ in range(N)]

#맨 윗줄

#맨 아랫줄
dp[-1][0]=cost_list[-1][0]
dp[-1][1]=cost_list[-1][1]
dp[-1][2]=cost_list[-1][2]

for i in range(N-2,-1,-1):
    for j in range(3):
        if j == 0:
            dp[i][j] = cost_list[i][j] + min(dp[i+1][1],dp[i+1][2])
        elif j==1:
            dp[i][j] = cost_list[i][j] + min(dp[i+1][0],dp[i+1][2])
        else:
            dp[i][j] = cost_list[i][j] + min(dp[i+1][0],dp[i+1][1])
        

print(min(dp[0]))