[백준 6359] 만취한 상범

문제

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

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 

2
5
100

예제 출력 1 

2
10

   

문제 풀이

테스트 케이스는 5이상 100이하이다.

즉 방이 최소 5개 존재한다는 것이다. 처음에 문제를 이해할 때는 짝수 번째는 2의 배수 홀수 번째는 3의 배수로 풀이하다가 잘못된 것을 알고

2번째는 2의 배수, 3번째는 3의 배수 4번째는 4의 배수, n번째는 n의 배수임을 깨닫게 되었다.

n = 5인 경우 (1 = open / 0 = close)

1	1	1	1	1
1	0	1	0	1
1	0	0	0	1
1	0	0	1	1
1	0	0	1	0

위 표를 보면 규칙이 각 라운드 마다 열거나 닫는 방 번호는 라운드의 배수임을 알 수 있다. 

즉, 방번호 % 라운드 == 0 인 경우 열린 문은 닫고, 닫힌 문은 열면 되는 간단한 문제이다.

if문을 사용해서 방번호 %라운드 ==0 조건을 사용해도 되지만 조건을 조금 더 간단하게 하는 방법이 있다.

해당 라운드의 배수인 방이 열려있으면 닫고 닫혀있으면 여는 방법이다.

충분히 생각해보고 소스코드를 참고하자

소스코드

// //  main.cpp //  Algorithm // //  Created by sw on 2018. 6. 25.. //  Copyright © 2018년 sw. All rights reserved. // #include <iostream> #include <algorithm> using namespace std; int main(int argc, const char * argv[]) {     // insert code here...     int testcase, room;     cin>>testcase;     while(testcase>0){         testcase--;         cin>>room;         int dp[101] = {0};  //dp 저장 변수(테스트케이스마다 초기화를 위해 while문 안에 선언)         for(int i=1;i<=room;i++){             for(int j=1; i*j<=room; j++){                 if(dp[i*j]==1) dp[i*j]=0;                 else dp[i*j]=1;             }         }         for(int i=1; i<=room; i++){             dp[0] += dp[i]; //dp[0]를 count로 사용                             //for문을 사용하고 싶지 않다면 위쪽 if문에서 dp[0]값을 더하거나 빼주면 됨.         }         cout<<dp[0]<<endl;  //문이 열린 갯수 출력     }     return 0; }