BOJ_6359_만취한 상범

문제 이름 : 만취한 상범 (6359번)

문제 분류 : 수학, 구현

작성 언어 : C

 

 

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

2
5
100

예제 출력 1

2
10

 

풀이

 

예제 입력1 에서 5 -> 5개의 방과 5번의 라운드진행시

1라운드 -> 1,2,3,4,5 열림

2라운드 -> 2,4 닫힘

3라운드 -> 3닫힘

4라운드 -> 4열림

5라운드 -> 5닫힘

->1,4 열림

약수

1 -> 1

2 -> 1 , 2

3 -> 1 , 3

4 -> 1 , 2 , 4

5 -> 1 , 5

 

-> 약수의 개수가 홀수 일때 열린다.

이를 응용해보면

제곱수일때 열린다.

 

ex) 100개의 방과 100개의라운드시 

열린방은

1,2,4,9,16

25,36,49,64,81 로

출력이 10개가된다.

 

 

작성 코드

#include <stdio.h>

int main()
{
	int n,x;
	scanf("%d",&n);
	int count;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x);
		int j = 1;
		count = 0;
        while(1)
        {
            if(j*j>x) break;
            else count++;
            j++;
        }
        printf("%d\n",count);
	}
}

 

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

6359번: 만취한 상범