안녕하세요
재재입니다.
BOJ 14927 전구 끄기 문제 풀이입니다.
BOJ 14927 전구 끄기
(1) 문제 설명
분류 : greedy, bruteforce
출처 : https://www.acmicpc.net/problem/14927
(18이하) N by N의 입력이 주어집니다.
전구 하나를 누르면, 상/하/좌/우 그리고 자신의 상태가 반전이 됩니다.
모든 전구를 끄기 위한 최소한의 횟수를 출력해주면 됩니다.
(2) 풀이 도출
최적의 전략은 없습니다.
단, 첫 줄의 상태를 정해주면 그 밑줄 부터는 최소한으로 전구를 끌 수 있는 방법이 있는데요.
(역시 불가능한 경우가 있습니다.)
첫 줄에 대한 $$ 2^18 $$ 의 모든 상태를 정해주고,
두 번째 줄부터 최적의 전략을 진행합니다.
여기서 최적의 전략은, 나의 바로 위의 전구가 켜져있는지만 확인하면 되는 전략인데요.
지금 채우고 있는 전구가 x번째 행이면, x-2번째이하의 행의 전구들은 모두 꺼져있습니다.
최적의 전략대로 전구를 끄되, 가장 마지막 줄의 전구가 꺼져있는지만 확인하면 되겠습니다.
전체 시간복잡도 $$ O(n^2 * 2^n) $$ 에 해결 가능합니다.
BOJ 14927 전구 끄기