[백준 2138] 전구와 스위치

[ 백준 2138 : 전구와 스위치 ]

백트래킹 문제

N의 범위가 10만이기 때문에 단순히 깊게 재귀를 하면 메모리 초과가 나버린다.
이런 문제들이 어려운 문제라고 생각한다.
단순하게는 푸는 방법을 알기 힘들고 일련의 규칙? 같은 것을 찾아야하는 문제들... 이 문제는 많이 생각이 필요했고 질문게시판의 글을 보고 깨닫게 되었다.

처음 풀었던 방식은

현재 인덱스의 스위치를 누를 것인가? 말것인가? 로 재귀적으로 파고 들어간다. 이렇게 풀면 메모리 초과가 난다.
그럼 어떻게 누를지, 말지를 더 줄일 수 있을까?

총 7개의 스위치가 있다고 가정하면

1번 전구에 영향을 주는 스위치는 몇 번 일까?
바로 1번과 2번이다.

그럼 2번 전구는? 1번과 2번 그리고 3번이다.

3번은 2번 3번 4번.
4번은 3번 4번 5번. 아마 여기까지는 문제에 나와있으니까 다들 알텐데

직접 그려보면 조금 더 규칙을 찾을 수 있다.

1번을 누르고 2번을 누른 결과와
2번을 누르고 1번을 누른 결과가 같다.

다른 번호들도 마찬가지이다.
이 말은 곧 1번부터 순서대로 누를지 말지를 결정해도 결과는 똑같다는 것이다.

그럼 재귀 함수를 먼저 이렇게 만들어 볼 수 있다.

VOID RECUR(INT IDX){ -> IDX는 인덱스를 가리키고 1번 2번 ... N번까지 간다.
IF(IDX==N)
RETURN;
}

이렇게 순서대로 IDX가 진행된다면 한 스위치를 누를 때 영향을 주는 것은 그 전 번호의 전구라는 것을 알 수있다.
그럼
인덱스를 1번 부터 시작할 필요가 없다. 왜냐면 1번이 제일 처음이고 그 전의 전구는 없으니까 바뀌고 말고 할 게 없다.

그럼 함수 내에서 재귀적으로 들어가야할 부분도 알 수 있다.

IDX를 기준으로 그 전 전구를 바꾸는 것이기 때문에
IDX버튼을 안눌렀을때 -> 결과로 나올 전구상태[IDX-1] 과 현재 전구상태[IDX-1] 이 같으면 같은 상태로 IDX+1 재귀를 들어간다.
IDX버튼을 눌렀을때 -> 결과로 나올 전구상태[IDX-1] 과 현재 전구상태[IDX-1] 이 같으면 같은 상태로 IDX+1 재귀를 들어간다. 이때는 카운트도 한 개 늘려줘야한다.

이렇게 IDX가 N까지만 가면된다.
N번 버튼을 눌렀을때와 안눌렀을때의 상태와 결과로 나올 전구상태를 비교해 일치하면 카운트를 답으로 출력해주면된다.
만약 카운트가 처음 설정한 값 그대로라면 -1을 출력한다.