상세 컨텐츠

본문 제목

RGB거리 2

코딩테스트/다이나믹 프로그래밍

by 수타. 2023. 9. 21. 17:12

본문

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

 

17404번: RGB거리 2

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

www.acmicpc.net

문제요약:

열의 길이 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]

'코딩테스트 > 다이나믹 프로그래밍' 카테고리의 다른 글

동전 2  (1) 2023.10.12
하노이 탑 이동 순서  (1) 2023.10.05
행렬 곱셈 순서  (0) 2023.09.13
평범한 배낭  (2) 2023.09.09
파괴되지 않은 건물  (0) 2023.07.17

관련글 더보기