[C++/알고리즘] 백준 6359 (만취한 상범)

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

6359번: 만취한 상범

 

 

문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

 

이렇게 감옥이 n개가 있는데 

첫 번째 잔을 마신 후에는 다 열고

두 번째 잔을 마신 후에는 2의 배수번 째 방을 다 잠그고

세 번째 잔을 마신 후에는 3의 배수 번 째 방을 확인하는데 잠겨있으면 열고 열려 있으면 잠근다.

즉, 두 번째 잔을 마신 후 잠궈놓은 2,4,6... 2의 배수 번째 방은 세 번 째 잔을 마신 후에는 겹치는 방인 6,12,18,24... 번째 방은 다시 열고 3,9,15,21... 번째의 방은 다 잠근다.

이렇게 n번째(=감옥의 방 개수) 잔까지 마신 후 끝난다.

 

생각보다 간단했다. 

일단 처음에 모든 방을 true로 바꿔준 후(첫 번째 방은 모두 다 열었으므로)

두 번째, 세 번째,... n번 째까지 돌면서 n의 배수번째 방을 확인하며 true이면 false로 false이면 true로 바꿔준 후 마지막에 true인 방의 갯수를 세었다. 

 

조금 비효율적으로 푼 것 같긴한데 차차 생각해볼 문제인 것 같다. 

#include <iostream>
#include <vector>
using namespace std;

const int MAX_ROOM = 100;


int Escape(int room)
{
	bool r[MAX_ROOM + 2];
	memset(r, true, sizeof(bool)*(room+2));
	for (int i = 2; i <= room; i++)
	{
		for (int j = 1; j <= room; j++) {
			if (j % i == 0) {			
				r[j] = !r[j];
			}
		}
	}

	int count = 0;
	for (int i = 1; i <= room; i++) {
		if (r[i]) {
			count += 1;
		}
	}
	return count;
}


int main()
{
	int T = 0;
	cin >> T;

	vector<int> TestCase(T + 1);

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

	for (int i = 1; i <= T; i++) {

		cout << Escape(TestCase[i]) << endl;
	}

}

 

 

 

내가 처음 문제를 읽고는 감옥의 갯수로 주어지는 n개와 상범이가 마시고 취하는 횟수인 n을 서로 다른 조건으로 보고 취하는 횟수는 언제 주는지 의아해했다.

(그럴 리가 없다고 생각했던 게 제일 컸던 것 같다. ;;) 

 

그리고 나는 visual studio 2017을 사용하는데 백준 문제를 제출할 때 memset을 쓰는 경우 헤더에

#include <memory.h>를 추가해야 컴파일 에러가 나지 않는다.