이거 어케품?

[익명(59.26)]

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

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

Baekjoon Online Judge

DP씨발진짜 존나어렵네

[Hrin(jghdsa6665)]

쉬운데 - dc App

[익명(59.26)]

힌트좀 점화식을 못찾겠음

[Hrin(jghdsa6665)]

그냥 완전탐색아니냐 - dc App

[익명(59.26)]

최악이 N = 1000에서 3^1000까지 갈 수 있어서 브루트포스나 DFS같은거로 풀면 시간초과날거같음

[익명(59.26)]

아니지 문제조건상 N = 1000에서 3 * 2^999네 이래도 가장빠른 언어로 돌려도 최악에선 무조건 시간초과임ㄷ

[Hrin(jghdsa6665)]

ㅇㅋ.. n번째 집을 r색으로 칠할때 최소비용을 dp[n][r]로 하면 dp[n][r] = min(dp[n-1][r+1] + cost[n][r], dp[n-1][r+2] + cost[n]) 이렇게 되는거 아님?? - dc App

[익명(59.26)]

결국 알고리즘 도식화한 블로그 찾아서 풀었음.. cost를 시각화한게 왤케 신기하냐 존나신기함..