[백준 BOJ] 1244번 스위치 켜고 끄기 (C++/cpp)

문제 설명

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

1244번: 스위치 켜고 끄기

 

접근 방법 - 시뮬레이션을 통한 구현 문제

백준의 1244번 문제는 시뮬레이션을 통하여 알고리즘을 구축하며 해결해야 하는 문제이다.

해당 문제는, 전구가 나열되어 있고 학생들에 의해서 특정 규칙에 따라 전구의 상태가 변할 때 마지막의 전구 상태들을 구하여 출력해야 하는 문제이다.

이때, 전구는 아래의 규칙에 따라 변하고 입력값에 따라 어떻게 변하는지 결정된다.

• 처음 전구의 상태를 입력받고 난 뒤, 1개 이상의 {gender, num} 쌍이 입력으로 주어진다. 
• gender가 1인 경우는 남학생이 전구의 상태를 변경함을 의미한다. 남학생은 num의 배수에 대한 전구의 상태를 모두 반대로 바꿔버린다.
• gender가 2인 경우는 여학생이 전구의 상태를 변경함을 의미한다. 여학생은 num번 전구를 중심으로 전구의 상태가 대칭이며 전구의 개수가 최대인 구간 속 모든 전구의 상태를 반대로 바꿔버린다.

여학생의 경우가 다소 설명이 난해한데, 문제에 있는 예시를 보면 보다 수월하게 파악할 수 있을 것이다.

 

시뮬레이션 문제이다 보니, 필자는 문제에 제시된 조건들을 그대로 코드로 작성하면서 해결하였다.

필자는 문제를 파악하는 데에 시간이 걸려 몇 번 시행착오가 있었지만, 문제 파악만 잘하면 어렵지 않게 풀 수 있는 문제일 것이다.

자세한 설명은 아래에 기재하니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 전구의 상태를 저장할 배열 bolb를 전역 변수로 미리 선언해 둔다.

 

2) 전구의 개수(n)와 처음 전구들의 상태(bolb)를 입력받는다.

 

3) 뒤이어, 학생 수(m)를 입력받는다.

 

4) m의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 학생의 성별(gender)과 임의의 숫자(num)를 입력받는다.

- 연산에 필요한 변수를 미리 설정해 둔다.

• 남학생인 경우의 연산에 사용할 변수 cnt는 1로 초기화하며 선언해 둔다.
• 여학생인 경우의 연산에 사용할 변수 left, right는 num 값으로 초기화하며 선언해 둔다.

- gender의 값에 따라 아래의 연산을 수행하도록 한다.

• 값이 1일 때엔, num의 배수인 전구 상태를 모두 반대로 바꾼다. num*cnt 위치의 전구 상태를 반대로 변경하고, 배수 연산을 위해 cnt는 1씩 추가해 주도록 한다.
• 값이 2일 때엔, num 중심부터 바깥쪽 방향으로 하여 전구의 상태가 대칭인지를 탐색한다. left는 1씩 줄이고 right는 1씩 늘리면서 bolb 값을 비교하는데, 같지 않은 순간이 오면 탐색을 종료하도록 한다.

이때, 필자는 change(index) 함수를 미리 구현해 두고 이를 통해서 전구의 상태를 변경하였다.

매개변수 값으로 받은 index 위치의 bolb 값을 반대로 변경하게끔 함수의 내용을 구현해 두었다.

 

5) 위 연산이 모두 끝났다면, 현재 저장되어 있는 bolb 값들을 순차적으로 출력하도록 한다.

이때, 한 줄에 최대 20개 전구의 상태를 출력해야 하기 때문에, % 연산자를 통해서 줄바꿈 연산을 제어하도록 한다.

정답 출력까지 완료하였다면, 실행을 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 1244번 코드
int bolb[101];
void change(int index) {
	if (bolb[index] == 0) {
		bolb[index] = 1;
	}
	else {
		bolb[index] = 0;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> bolb[i];
	}

	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int gender, num;
		cin >> gender >> num;

		int cnt = 1;
		int left = num;
		int right = num;
		switch (gender) {
		case 1:		// 남학생인 경우
			while (num * cnt <= n) {
				change(num * cnt);
				cnt++;
			}
			break;
		case 2:		// 여학생인 경우
			while ((left > 0 && right <= n) && bolb[left] == bolb[right]) {
				if (left == right) { change(left); }
				else {
					change(left);
					change(right);
				}

				left--;	right++;
			}
			break;
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << bolb[i] << " ";
		if (i % 20 == 0) { cout << endl; }
	}
	cout << endl;
}

 

제출 결과

(2023.09.10 백준 1244번 문제 제출 결과)

문해력을 길러야겠다...