[백준] 14586 도미노 (Small)

14586번: 도미노 (Small)

 

 

풀이 아이디어

 

모든 도미노를 순회하면서

i번째 도미노를 왼쪽으로 넘어트렸을 때 

 

연쇄 반응이 완료되는 지점에서 -1인 o

dp[i] = min (dp[i] , dp[o] + 1) 

 

i번째 도미노를 오른쪽으로 넘어트렸을 때

 

연쇄 반응이 완료되는 지점인 k

dp[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 이런식으로 배치된다면 해를 내지 못하게 된다.

 

 

최적화하기

 

똑같은 조건으로 n이 50만인 문제가 존재하기 때문에 더 빠른 방법이 존재하다.

추측하건데 연쇄반응이 끊기는 지점을 더 빠르게 풀면 되는데 확실하게 최적화 할 방법이 생각나진 않는다.

태그가 세그먼트 트리인걸로 봐서 O(NlogN)...