14586번: 도미노 (Small) 풀이 아이디어 모든 도미노를 순회하면서i번째 도미노를 왼쪽으로 넘어트렸을 때 연쇄 반응이 완료되는 지점에서 -1인 odp[i] = min (dp[i] , dp[o] + 1) i번째 도미노를 오른쪽으로 넘어트렸을 때 연쇄 반응이 완료되는 지점인 kdp[k] = min(dp[i-1] + 1 , dp[k])를 dp로 계산해서 n-1 지점을 출력하면 된다. n이 300임으로 연쇄반응이 끊기는 지점을 순회해서 돌더라도시간복잡도 O(n^2)안에 풀 수 있다. 시행착오 처음에는 유니온파인드와 그리디를 이용하여 가장 많이 넘어트릴 수 있는 도미노를 구해서 풀리는가 생각해봤는데 도미노가1 1 1 1 10 5 4 3 2 1 이런식으로 배치된다면 해를 내지 못하게 된다. 최적화..