백준 6359번 만취한 상범

만취한 상범 성공출처다국어분류

시간 제한메모리 제한제출  정답맞은 사람정답 비율

1 초

128 MB

7641

5227

4452

69.978%

문제

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

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

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

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

입력

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

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

예제 입력 

2 5 100

예제 출력

2 10

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        int cnt = 0;
        cin >> n;
        vector<int> v(n+1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*i <= n; j++) {
                if (v[i * j] == 0) {
                    v[i * j] = 1;
                }
                else {
                    v[i * j] = 0;
                }
            }
            
        }
        for (int i = 1; i < v.size(); i++) {
            if (v[i] == 1) {
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

방 갯수만큼 for문을 돌리면서 각 방(v)의 값이 0인지 1인지 판별하면 쉽게 풀리는 문제였다.
방의 값이 0이면 1, 1이면 0으로 바꿔준 후 해당 반복문이 끝났을때 그 수를 세어 출력해주면 끝!

오랜만에 브론즈 문제라 마음이 편-안...