https://www.acmicpc.net/problem/6359
6359번: 만취한 상범
한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.
www.acmicpc.net
🔔 문제 :
방이 (5<=n <=100)인 n개가 있습니다.
처음에는 방은 모두 닫혀있고,
처음엔 1,2,3,4 ... n 까지 열고 닫고,
두번짼 2, 4, 6, ... 번 방을 열고 닫고,
k번짼 k의 배수 방이 열고 닫고, 하는 규칙을 가지고 있습니다.
1번쨰부터 n번째까지 순서대로 규칙에 따라 방문을 열고 닫는다 할 때,
최종적으로 문이 열려있는 방문의 개수를 출력하는 문제입니다.
🔔 Kick Point :
규칙을 찾아야하는 DP 문제입니다.
하지만 저는 100개 밖에 없는 방이여서, 편하게 일일히 다 방을 닫고 열고 하여, 브루탈로 찾아냈습니다.
🔔 Code :
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
bool room[101] = { false, };
for (int i = 1; i <= n; i++) {
for (int j = 1; i*j <= n; j++) {
room[i*j] = !room[i * j];
}
}
int cnt(0);
for (int i = 1; i <= n; i++) {
if (room[i]) cnt++;
}
cout << cnt << endl;
}
}