https://www.acmicpc.net/problem/17404
17404번: RGB거리 2첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나www.acmicpc.net
처음에 엄청 헤멨다.
처음 집을 칠하는 경우가 3가지니 3가지 경우의 수를 두고 dp를 구하는 것까진 생각했으나, 코드가 너무 복잡했다.
처음 집 0을 칠하는 경우를 예로 들면
두번째 집에서는 0을 칠하지 못하므로 이를 제외한경우의 수를 구하는데………..
…………………………
그냥 너무 복잡했다.
그러다가 나온 결론이
엄청 큰 값을 줘버려서 0 이외의 다른 숫자들은 선택조차 못하게 하자! 였다.
dp[i][n]=max(dp[i-1][1],dp[i-1][2])+cost[i][n]인데,
만일 처음에 0번집 외의 집을 엄청 큰 값을 주면,
두번째 1,2 번 집에서는 무조건 0번집에서 시작한 결과로 이어질 것이고,
두번째의 0번집에선 첫번째의 엄청 큰 값을 계승할 수밖에 없으므로
자연스럽게 3번째 집을 구할 때 제외되게 된다.
그리고 마지막 집은 0과 달라야 하므로, 마지막 집의 1,2중 최솟값이 리스트에 추가된다.
이를 0, 1,2 각각에 대해 구하고, 이 모든 최솟값 중 최솟값을 구하면, 답이 나온다.
n=int(input())cost=[]for _ in range(n):
cost.append([* map(int,input().split())])answer=[]for i in range(3):
n_list=[0,1,2] n_list.remove(i) dp=[[0,0,0] for _ in range(n)]
dp[0][i]=cost[0][i] for num in n_list: dp[0][num]=5000
for j in range(1,len(dp)):
dp[j][0]=min(dp[j-1][1],dp[j-1][2])+cost[j][0]
dp[j][1]=min(dp[j-1][0],dp[j-1][2])+cost[j][1]
dp[j][2]=min(dp[j-1][0],dp[j-1][1])+cost[j][2]
a=min(dp[n-1][n_list[0]],dp[n-1][n_list[1]]) answer.append(a)
print(min(answer))숏코딩 봤는데 은근 정상적인 코드인데 이해할수가 없다.
다음에 생각나면 한번 다시봐야겠다.
숏코딩 코드(내꺼아님)
n=int(input())l=[list(map(int,input().split())) for _ in range(n)]s=9**9
for k in range(3): d=[[0,0,0]for _ in range(n)] d[-1]=list(l[-1])
d[-1][k]=9**9 for i in range(n-1): x=n-2-i
for j in range(3):
d[x][j]=l[x][j]+min(d[x+1][j-1],d[x+1][j-2]) s=min(s,d[0][k])
print(s)