[파이썬] 백준 17404 : RGB거리 2 (골드4)

[파이썬] 백준 17404 : RGB거리 2 (골드4)

 

17404번: RGB거리 2

---

문제

---

풀이

0. 방향성 생각

각 색깔별로 시작해서 마지막에는 자신과 다른 색으로 끝난 색의 값 2개씩 받는다.

총 6개 중 최소값을 출력.

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int,input().split())))

2. 함수 정의

def min_cost(idx):
    dp = [[0,0,0] for _ in range(n)]
    dp[0] = [10**6+1]*2
    dp[0].insert(idx,arr[0][idx])
    for dist in range(n-1):
        for color in range(3):
            if color == 0 :
                dp[dist+1][0] = arr[dist+1][0] + min(dp[dist][1],dp[dist][2])
            elif color == 1 : 
                dp[dist+1][1] = arr[dist+1][1] + min(dp[dist][0],dp[dist][2])
            elif color == 2 : 
                dp[dist+1][2] = arr[dist+1][2] + min(dp[dist][1],dp[dist][0])
    cost = dp[-1]
    cost.pop(idx)
    return cost

임의의 색깔에서 출발해서 출발 색깔이 아닌 다른 색에서 끝나는 값 2개씩 얻는다.

제일 중요한 점은 DP 시작 색깔이 마지막 색깔과 달라야한다.

R을 골랐으면 시작점의 G B는 다음 거리에서 절대 선택될 수 없게 10**6+1로 초기화시켜준다.

DP 시작값을 모두 R 값으로 채우면 안되냐? -> 다음 배열에 영향을 줄 수 있음.

다음 DP R값 = 다음 arr R값 + 이전 G/B 중 최소값. 이런식으로 DP 배열을 채워준다.

 

3. 출력

answer = []
for i in range(3):
    answer.extend(min_cost(i))
print(min(answer))

답에는 R->G,B / G->R,B / B->R,G 총 6개의 결과가 들어있게 된다.

answer에 후보 6개를 넣어주고 그 중 최소값 출력한다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int,input().split())))

def min_cost(idx):
    dp = [[0,0,0] for _ in range(n)]
    dp[0] = [10**6+1]*2
    dp[0].insert(idx,arr[0][idx])
    for dist in range(n-1):
        for color in range(3):
            if color == 0 :
                dp[dist+1][0] = arr[dist+1][0] + min(dp[dist][1],dp[dist][2])
            elif color == 1 : 
                dp[dist+1][1] = arr[dist+1][1] + min(dp[dist][0],dp[dist][2])
            elif color == 2 : 
                dp[dist+1][2] = arr[dist+1][2] + min(dp[dist][1],dp[dist][0])
    cost = dp[-1]
    cost.pop(idx)
    return cost

answer = []
for i in range(3):
    answer.extend(min_cost(i))
print(min(answer))

 

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
inf = 1e9

def find_cost(rgb):

    dp = [[0]*3 for _ in range(n)]
    dp[0] = [1e9]*3
    dp[0][rgb] = arr[0][rgb]

    for stage in range(n-1):
        for nc in range(3):
            dp[stage+1][nc] = min(dp[stage][c] for c in range(3) if c != nc) + arr[stage+1][nc]

    return min(dp[-1][c] for c in range(3) if c != rgb)

print(min(find_cost(ans) for ans in range(3)))

다시 풀어본 풀이
다시 보니까 배열을 크게 만들어주는게 아니면, dp를 여러번 반복해서 풀 수 있다.
초기 state가 x개로 정해지면 x번 반복해서 도출된 output 중 결과를 선택하는 방식