[Python] BOJ 1149 RGB거리 (dp)

BOJ 1149

🕵️‍♀️ 문제

---

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보다 작거나 같은 자연수이다.

 

 

 

📌 출력

---

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

 

 

🙋‍♀️ 풀어보자~

---

다이나믹 프로그래밍으로 접근해서 Memoization을 사용하자.

 

2차원 배열을 이용해서 각 자리마다 RGB의 비용을 담을 수 있게 하자.

just like... -> [ [ 1번 집의 R비용, 1번 집의 G비용, 1번 집의 B비용 ] , [ 2번 집의 R비용, ....

 

점화식을 떠올리기 위해서 i번째의 집과 그 앞뒤의 i-1번째 집과 i+1번째 집을 생각해보자.

i+1번째 집은 i번째 집의 색에 영향을 받지만 i-1번째 집의 색에는 영향을 받지 않는다.

 

 

이 같은 상황을 점화식으로 생각해보자. i와 i+1만 생각해주면된다~

1. i+1번째 집이 R일 때, i-1은은 G나 B 중 더 적은 비용을 갖는 것을 선택하면 된다.
2. i+1번째 집이 G일 때, i-1은은 R나 B 중 더 적은 비용을 갖는 것을 선택하면 된다.
3. i+1번째 집이 B일 때, i-1은은 R나 G 중 더 적은 비용을 갖는 것을 선택하면 된다.

 

 

 

# RGB

# n : 집의 수
n = int(input())

# 초기세팅 0으로 다 깔아놓거라
dp = [[0, 0, 0] for _ in range(n)]

for i in range(n):
    # 우선 먼저 입력받음
    cost = list(map(int, input().split()))

    # 첫 입력인 경우, 그냥 cost를 담아주세요.
    if i == 0:
        dp[0] = cost
    else:
        # 점화식 넣어주세효
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[0] # i번째집이 R일경우
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[1] # i번째집이 G일경우
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[2] # i번째집이 B일경우

# dp 리스트의 n-1번째에 있는 누적된 RGB 비용 중 가장 최소 값을 출력한다.
print(min(dp[n-1]))