[C++] 백준 15729번 방탈출

1. 문제이해

https://www.acmicpc.net/problem/15729

15729번: 방탈출

 

혜민이는 모두 불이 꺼진 상태에서 버튼을 최소로 눌러, 쪽지와 똑같은 상태로 만들려고 한다.

버튼을 누르는 방식은 다음과 같을 때, 눌러야 하는 버튼의 최솟값을 구하는 것이 목표이다.

 

1.  앞에는 일렬로 놓여진 N개의 버튼이 모두 불이 꺼진 상태로 있다.

2. 0 또는 1로 구성되어 있는 N자리 수가 적힌 쪽지가 있다.

3. 0은 불이 꺼진 버튼, 1은 불이 켜진 버튼을 뜻한다.

4. 불이 켜져 있는 버튼을 누르면 불이 꺼지고, 불이 꺼져 있는 버튼을 누르면 불이 켜진다.

5. 버튼을 누르면 그 버튼 뿐만이 아닌 오른쪽 두 개의 버튼도 같이 눌린다. 

 

 

 

2. 문제풀이

 

불이 모두 꺼진 상태에서, 쪽지와 같은 상태로 만드는 것이 목표이다.

버튼을 한개 누르게 되면, 해당 버튼의 오른쪽 1, 2번째 버튼도 함께 눌리게 되며,

버튼을 누르면 켜져있던 불은 꺼지고, 꺼져있던 불은 켜지게 된다.

 

불이 모두 꺼진 상태에서 쪽지와 같은 상태로 만드는 방식은 꽤나 복잡하므로,

다르게 접근해 볼 필요가 있다.

불이 모두 꺼진 상태에서 쪽지와 같은 상태로 만드는 것,

즉, 반대로 접근해보면, 쪽지와 같은 상태의 불들을 모두 끄는 것과 같다.

이 점에 착안하여 작성한 소스코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int room[1000000];

int main() {
	int N;             // 버튼의 개수
	int count = 0;     // 버튼을 눌러야 되는 횟수

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> room[i];
	}

	//켜져있는 버튼을 찾아 모두 꺼야함
	for (int i = 0; i < N; i++) {
		if (room[i] == 1) {
			count++;	// 버튼을 눌려야 하는 횟수++

			// 오른쪽 1번째 버튼 눌림 
			if (room[i + 1] == 1) {
				room[i + 1] = 0;
			}
			else {
				room[i + 1] = 1;
			}
			// 오른쪽 2번째 버튼 눌림 
			if (room[i + 2] == 1) {
				room[i + 2] = 0;
			}
			else {
				room[i + 2] = 1;
			}
		}
	}

	cout << count;

	return 0;
}

먼저, 버튼의 개수(N)와 쪽지에 적힌 버튼의 상태(room) 를 입력받는다.

최종적으로 버튼을 눌러야 하는 횟수(count)는 0으로 초기화시킨다.

 

2. 문제풀이에서 도출한 풀이방식에 따라, 켜져있는 불들을 모두 꺼주면 되므로,

 for문을 통해 버튼이 눌려있는 경우, 즉 불이 켜져있는 경우를 찾는다.

불이 켜져있는 버튼을 찾았다면, 해당 버튼을 누르고, (room[i] = 0 / 꺼진 상태로 바꾼다.)

버튼을 누른 횟수를 증가시킨다. (count++)
오른쪽 1번째, 2번째 버튼도 같이 눌리게 되므로, 해당 버튼들도 상태를 바꾸어준다.

(켜져있다면 꺼주고, 꺼져있다면 켜준다.)

 

모든 연산이 끝나고 나면, 버튼을 누른 횟수(count)를 출력한다.

 

 

---

반대로 접근해보면 나름 괜찮은 문제였다.

필자는 반대로 생각하지 못해서 헤맸다..😥

코딩은 언제나 그렇듯 더 좋은 방안을 생각하는게 참 중요한 작업인 것 같다.