[파이썬] 단계별 백준 문제 풀기 - 1149 동적 계획법 1 (RGB거리)

문제링크

1149번: RGB거리

문제

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

출력

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

 

---

<<소스코드>>

import sys
n = int(sys.stdin.readline()) #집의 갯수
home = []

# for문으로 입력받은 색칠 비용을 home[] 빈 리스트에 넣어준다
for i in range(n):
    home.append(list(map(int,sys.stdin.readline().split())))

#dp 리스트에 입력받은 갯수만큼 0으로 된 리스트를 만들어준다. 3열, n행(집의갯수만큼)
dp = [[0 for _ in range(3)] for _ in range(n)]

#0부터 n-1까지 dp 리스트를 채워줄 예정, 최솟값들의 경우의 수가 들어간다.
#0일때는 첫째집이니 기존 값(home)으로 채워줌. 비교는 두번째 집부터
#0은 R, 1은 G, 2는 B를 의미함

for i in range(0,n):
    if i == 0:
        dp[0][0], dp[0][1], dp[0][2] = home[0][0], home[0][1], home[0][2]
    else:
        dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + home[i][0]
        dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + home[i][1]
        dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + home[i][2]

print(min(dp[n-1])) #마지막줄의 최솟값 

<<결과값>>

3
26 40 83
49 60 57
13 89 99

96

---

문제의 조건은 바로 옆의 집이 같은 색만 아니면 된다.

두번째 집을 기준으로 앞, 뒤 집이 다른색깔인지 확인하는 점화식을 세워준다.

아래 수식을 예제의 표를 대입하여 그려보았다. 

첫째줄은 그대로 두고, 둘째줄 기준으로 자신과 동일한 색상을 제외한 나머지 2개의 색상 중 최솟값을 첫째줄에서 골라준다. 

마지막줄에서 3개의 값을 더한 경우의 수 중에서 최솟값을 찾아 출력해주면 된다! 

        dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + home[i][0]
        dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + home[i][1]
        dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + home[i][2]

 

다양한 형태의 리스트 표현식 알고가기!! 

import sys
home = list(map(int,sys.stdin.readline().split()))

#3열, n행일 때
dp = [[0 for _ in range(3)] for _ in range(n)]