[BOJ] #6359 만취한 상범

시간 제한	메모리 제한	정답 비율
1 초	128 MB	69.799 %

 

6359번: 만취한 상범

문제

n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.

첫 번째 라운드에서 상범이는 모든 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠곡, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

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

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

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5 ≤ n ≤ 100)이 주어진다.

 

메모리	시간
1999 KB	0 ms

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t, n, ans;
int prison[105];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= n; j += i) {
                prison[j] = prison[j] ? 0 : 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!prison[i]) ans++;
        }
        printf("%d\n", ans);
        ans = 0;
        memset(prison, 0, sizeof(prison));
    }
    
    return 0;
}

 

띠요오옹
좀 만 생각하면 이렇게 나온답니다 ^^.. 루트 값이네..... 이 부분은 다음 주 스터디 할 때 의논하기..

#include<stdio.h>
int main() {
    int i, t, n; scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i = 1; i*i <= n; i++);
        printf("%d\n", i-1);
    }
    return 0;
}