[백준 10258번] 스위치 배열

난이도: 골드 I

문제 링크: https://www.acmicpc.net/problem/10258

10258번: 스위치 배열

 

백준 10258번 문제 스위치 배열

이 문제의 경우에는 제가 어디 다른곳에서 봤다가... 해결을 못했었는데

이후에 더 고민해서 답을 찾았던 문제입니다. 마침 백준에 있길래 그대로 제출했고 정답 판정을 받았네요!

 

규칙이 딱 두 개 존재합니다.

1. 가장 오른쪽의 스위치를 토글한다.
2. i + 1번째 스위치가 1이고, i + 2부터 그 뒤까지 전부 0일 때, i번째 스위치를 토글한다.

이 문제는 수학 문제라고 판단하고, 패턴을 찾기 위해 노력했습니다.

제가 제일 먼저 찾은 패턴은 다음과 같습니다.

1. 두 패턴을 번갈아서 적용할 때가 최소 토글 횟수가 된다.
2. 맨 처음에 2번 규칙을 적용할 수 있는 경우, 둘 중 어느 규칙을 먼저 적용해야 최소 토글 횟수가 되는지는 모른다.

저는 이 방법을 바탕으로 규칙 1과 2를 각각 함수로 분리하고, 0이 될 때까지 규칙 2와 1 (1이 마지막이 되어야 합니다)을 반복하는 식으로 하였으나, 시간 초과에 걸렸습니다.

따라서 이를 더 빨리 해결할 수 있는 방법을 찾아 고민하게 되었습니다.

 

제가 찾아낸 새로운 규칙은 다음과 같습니다.

1. 입력이 100으로 들어올 경우, 100 -> 101 -> 111 -> 110 -> 010 -> 011 -> 001 - > 000 으로, 토글은 총 7회 수행되었다. 이는 2^3 - 1과 같은 수치이며, 주어진 입력의 경우 2^2와 같다. 따라서 가장 첫 자리만 1이고 나머지가 0인 입력의 경우, 최소 토글 횟수는 맨 오른쪽 자릿수를 1이라고 할 때, pow(2, i) - 1이 된다.
2. 입력이 110으로 들어올 경우, 110 -> 010 -> 011 -> 001 -> 000 으로, 토글은 총 4회 수행된다. 주목할 점은, 입력이 10으로 들어오는 경우, 10 -> 11 -> 01 -> 00 으로, 토글은 총 3회 수행된다. 110의 토글 횟수는 100의 토글 횟수에서 10의 토글 횟수를 뺀 만큼이다.
3. 따라서 101010과 같은 입력이 주어진다면, 토글 횟수 n = ((2^6 - 1) - (2^4 - 1) - (2^2 -1)) = 2^6 - 2^4 + 2^2 + 1 와 같은 방법으로 답을 구할 수 있다.

위 방법의 경우 최대 길이 (31)만큼의 입력이 들어와도, 모두 1이라는 가정 하에, 즉 최악의 경우에 31번의 연산 내로 답을 구할 수 있습니다.

 

제가 접근한 방법이 출제자가 의도한 정답인지는 잘 모르겠습니다.

하지만 주어진 테스트케이스를 통과했기에, 이 방법 또한 정답 중 하나라고 생각됩니다.

정보를 더 얻고 싶어 검색을 해 본 결과, 다음과 같은 설명을 찾을 수 있었습니다.

 

https://gooddaytocode.blogspot.com/2016/05/boj.html

위 링크에서 슬라이드 중 10258번: 스위치 배열에 대한 설명을 찾을 수 있습니다 (슬라이드 70부터 시작).

해설에서는 000....000에서 주어진 입력으로 만드는 접근 방식을 소개하였는데, 구체적으로는 오른쪽으로부터 i번째 비트를 0에서 1로 바꾸려면 2^(i-1)번의 토글이 필요하며, 토글하기 위해서는 반드시 오른쪽 비트를 바꾸어야 한다고 합니다.

접근하는 방법은 다르지만 큰 맥락에서는 제 방법과 유사한 것 같습니다.

 

채점 결과

수학 문제는 무언가 배경 지식이 필요한 경우도 많지만, 많은 경우 문제 안에 숨어 있는 패턴을 찾는 과정이 핵심 같습니다.

그만큼 알고리즘만 공부해서는 쉽게 풀 수 없고, 다양한 문제를 풀어보는 경험이 중요하다고 생각되네요.