https://www.acmicpc.net/problem/17404
17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
문제요약:
열의 길이 n이주어 지고 각 열에 들어갈 3개의 정수들이 주어집니다.
다음과 같은 세개의 조건을 만족할 때, 최소의 비용을 구하여라
난이도:
골드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 |