RGB거리 2

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

문제요약:

열의 길이 n이주어 지고 각 열에 들어갈 3개의 정수들이 주어집니다. 

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

다음과 같은 세개의 조건을 만족할 때, 최소의 비용을 구하여라

 

난이도:

골드4

 

소요시간:

@+ 20분

 

코딩:

import sys
input = sys.stdin.readline

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

ans =int(1e9)

for i in range(3):
    dp = [i[:] for i in arr]
    for t in range(3):
        if i!=t:
            dp[0][t] = int(1e9)
            
    for y in range(1,n):
        for x in range(3):
            temp = int(1e9)
            for k in range(3):
                if x!=k and temp>dp[y-1][k]:
                    temp =dp[y-1][k]
            dp[y][x] += temp

    for t in range(3):
        if i!=t and ans > dp[-1][t]:
            ans = dp[-1][t]
print(ans)

이전에 dp+ 그리디로 시도해봤다가 실패한 후 이번엔 그리디 이지만 시작할 때의 값을 정해주어서 1로 시작했을 때 2,3으로 시작했을때로 각각 정한 뒤 그들중 최소를 구했습니다. 선택하지 않는것은 일부러 최대값인 1000보다 큰값을 사용해 무조건 그 선택한 번호로 시작 하게 했습니다.

 

또한 배열을 복사할때, 그냥 할당하게 되면 수정했을 때 원본도 같이 바뀌기 때문에, 깊은 복사를 해주어야 하는데, 함수를 쓰는것 보다, 슬라이싱이 훨씬더 빠르기 때문에, (이유는 정확히 모르겠습니다.) 다음과같이 슬라이싱 을 이용하는것이 좋아보입니다.

1차원 배열일 때 temp = arr[:] 

2차원 배열일 때 temp = [i[:] for i in arr]