Algorithm/Acmicpc
2138 전구와 스위치 [JAVA]
문제 분석https://www.acmicpc.net/problem/2138N가능한 최소의 스위치 조작으로 주어진 전구 배열을 정답 배열로 만들려하는데 이때 드는 비용(횟수)을 구하는 문제이다. 처음 시도한 풀이는 아래와 같다.맨 마지막 2개의 전구에 대해서 그 앞의 전구까지 가능한 최소의 비용으로 스위치 조작을 해서 정답 배열과 일치시켜 오게 된다면 이를 3개짜리 전구를 조작하는 문제로 변경할 수 있다고 생각했다.즉, 1010111000 -> 00000000 이런 배열에 대해서 결국에는 0 a b -> 0 0 0 이 상태가 되는 문제로 변경할 수 있게 된다.따라서 3개의 전구에 대해서 각각 최소의 스위치 조작으로 정답 배열과 일치시킬 수 있다면 해당 횟수를, 없다면 -1을 리턴하는 방식으로 구현했었다. ..
