[BOJ] 17359 - 전구 길만 걷자

문제 출처

[BOJ] 17359 - 전구 길만 걷자

 

풀이

전구 묶음을 적절히 이어 전구 상태가 바뀌는 횟수를 최소로 하는 것을 목표로 하는 문제였습니다.

 

N이 10으로 10!이어도 시간이 충분하기 때문에 전구 묶음의 배치는 완전 탐색으로 구성하면 됩니다. 

 

하지만 완전 탐색을 돌릴때 묶음의 조합이 완성되어 이어진 묶음에서 전구 상태가 몇번 바뀌는지 매번  확인하게 되면 시간초과가 납니다.

각 전기 묶음의 전구 상태가 몇번 바뀌는지 미리 저장해놓고 각 전기 묶음이 이어지는 부분에서 전구의 상태가 바뀌는지만 확인해주어 시간초과를 해결할 수 있습니다.

 

코드

small-j/Algorithm