[백준][Python][17404][DP] RGB거리 2
문제 : https://www.acmicpc.net/problem/17404
17404번: RGB거리 2
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
www.acmicpc.net
DP 문제인데 정말 어려웠다.
이 문제는 RGB거리 와 비슷한데, 마지막 집과 첫번째 집이 인접한 원형 형태로 구성되어 있다고 한다.
그래서 마지막 답을 구할때, 첫번째에 어떤 집을 선택했나를 확인해야 한다.
dp 배열의 의미는 다음과 같다
dp[RGB 색, 각각 0,1,2] [ 0-(n-1)번째 집] 이다.
일단, 처음에 어떤 색을 선택했나 R,G,B 다 돌아볼 수밖에 없다.
initcolor 를 각각 0,1,2 즉 R,G,B 로 해서 for 문을 돌린다.
그리고, dp 배열의 첫번째 원소는 initcolor는 input 값과 같게, 나머지는 엄청 큰 수로 선택한뒤, RGB거리 처럼 하면 된다.
그리고 첫번째로 선택한 각각의 선택지에 대해 최솟값을 구해서 답을 제출하면 된다.
이때도, 3개의 마지막 배열값중 initcolor와 같은 선택지는 빼줘야한다.
참고로, 912344123412 이런숫자는 의미없는 큰숫자다.
https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
Nothing-up-my-sleeve number - Wikipedia
In cryptography, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized const
en.wikipedia.org
맨날 up ,on 헷갈린다. 블로그 어디에는 on으로 적혀있을듯
import sys
n = int(input())
m = []
for _ in range(n):
m.append([int(i) for i in sys.stdin.readline().split()])
ret = 99123443214231
for initcolor in range(3):
dp = [[0 for _ in range(n)] for _ in range(3)]
for i in range(3):
if i == initcolor:
dp[i][0] = m[0][i]
continue
dp[i][0] = 9123443214231
for i in range(1,n):
dp[0][i] = m[i][0]+min(dp[1][i-1],dp[2][i-1])
dp[1][i] = m[i][1]+min(dp[0][i-1],dp[2][i-1])
dp[2][i] = m[i][2]+min(dp[0][i-1],dp[1][i-1])
for i in range(3):
if i == initcolor:
continue
ret = min(ret, dp[i][-1])
print(ret)