문제
서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.
그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.
구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.
방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.
입력
입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5 ≤ n ≤ 100)이 주어진다.
출력
한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.
풀이
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
int main()
{
vector<vector<bool>> arr;
vector<int> res;
int t, n;
cin >> t;
res.assign(t, 0);
for (int i = 0; i < t; i++) {
cin >> n;
vector<bool> temp(n, false);
arr.push_back(temp);
}
for(int i=0; i<t; i++)
for (int j = 1; j <= arr[i].size(); j++) {
for (int z = 0; z < arr[i].size(); z++) {
if (j == 1) {
arr[i][z] = true;
continue;
}
if ((z + 1) % j == 0)
arr[i][z] = !arr[i][z];
}
}
for (int i = 0; i < t; i++) {
for (int j = 0; j < arr[i].size(); j++) {
res[i] += arr[i][j];
}
cout << res[i] <<'\n' ;
}
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준 1697] 숨바꼭질 / C++ (0) | 2020.08.12 |
---|---|
[백준 1260번] DFS와 BFS / C++ (0) | 2020.08.11 |
[백준 1932번] 정수 삼각형 / C++ (0) | 2020.08.10 |
[백준 2163번] 초콜릿 자르기 / C++ (0) | 2020.08.10 |
[백준 3943번] 헤일스톤 수열 / C++ (0) | 2020.08.08 |