백준(BOJ) 6359번 만취한 상범

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

문제

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

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

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

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

나의 풀이:

N이 200이라 완전 탐색으로 푸는게 가능할 것 같아서 완전 탐색으로 풀었습니다. check 배열을 만든 후 check[0] ~ check[N] 을 하나의 감옥으로 봅니다.

처음에는 모든 감옥이 잠겨있으므로 false 이고 한번 들렸다면 cnt를 +1 해주면서 false를 true로 만들어 줍니다. 열린 감옥을 

다시 방문한다면 cnt를 -1 해주고 false로 만들어줍니다.

코드 ( C ++ )

#include <iostream>

#include <cstring>

using namespace std;

int N;

int cnt;

// 감옥의 수

bool check[201];

void solve(int x)

{

// 감옥의 개수 이상 방문시 return 해준다.

if (x > N) return;

for (int i = x; i <= N; i += x) {

// 감옥이 열려있는 상태이니 닫아준다. 개수를 빼준다.

if (check[i] == true) {

cnt--;

check[i] = false;

}

// 감옥이 닫혀있는 상태이니 열어준다. 개수를 더해준다.

else if (check[i] == false) {

cnt++;

check[i] = true;

}

}

solve(x + 1);

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

int C;

cin >> C;

while (C--) {

cnt = 0;

memset(check, 0, sizeof(check));

cin >> N;

// 첫번째 방부터 시작한다.

solve(1);

cout << cnt << "\n";

}

return 0;

}