Baekjoon 백준 6359번 만취한 상범

만취한 상범 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	766	557	483	75.234%

문제

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

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

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

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

입력

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

출력

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

예제 입력 

2
5
100

예제 출력 

2
10

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2002 Greater New York Programming Contest B번

• 문제의 오타를 찾은 사람: onjo0127 wkd48632
• 문제를 번역한 사람: yh0413

링크

• ACM-ICPC Live Archive
• PKU Judge Online
• ZJU Online Judge
• TJU Online Judge
• HDU Online Judge

알고리즘 분류

• 다이나믹 프로그래밍

#include <stdio.h>

int main(){

int prison[1000], room, i, j, k, l, m, t, sum = 0;

scanf("%d", &t);

for(i = 0; i < t; i++){

sum = 0;

scanf("%d", &room);

for(j = 0; j < room; j++){

prison[j] = 1;

}

for(k = 2; k <= room; k++){

for(m = k; m <= room; m+=k){

if(prison[m - 1] == 1)

prison[m - 1] = 0;

else if (prison[m - 1] == 0)

prison[m - 1] = 1;

}

}

for(l = 0; l < room; l++){

sum += prison[l];

}

printf("%d\n", sum);

}

}

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