6359번 만취한 상범
(클릭시 새창으로 이동)
이 문제의 요지는 이렇다.
우선 첫 입력을 받는데 몇개의 테스트를 진행할 것인지 그 수를 넣는 것이다.
예제에서는 처음 2를 입력했고 두번 테스트를 하겠다는것.
그래서 차례로 5와 100을 넣은것이다.
처음부터 보면 2를 입력하고 5를 입력했다.
여기서 5를 입력했을시 진행되는 과정을 보자
5를 입력했기 때문에 1번방부터 5번방까지 있는 것이다.
1의 배수부터 2의 배수, 3의 배수 . . . 5의배수까지 진행될 것이다.
진행 과정중에 해당되는 칸이 열려있으면 닫고 닫혀있으면 열린다!
그리고 일단 감옥이므로 닫혀있다!
첫번째 1의 배수 : 모두 닫혀있으니 모두 연다
|
방번호 |
1 |
2 |
3 |
4 |
5 |
|
Open/Closed |
Open |
Open |
Open |
Open |
Open |
두번째 2의 배수 : 열려있으면 닫고 닫혀있으면 열린다
방번호 1 2 3 4 5 Open/Closed Open Closed Open Closed Open
세번째 3의 배수 : 열려있으면 닫고 닫혀있으면 열린다
방번호 1 2 3 4 5 Open/Closed Open Closed Closed Closed Open
네번째 4의 배수 : 열려있으면 닫고 닫혀있으면 열린다
방번호 1 2 3 4 5 Open/Closed Open Closed Closed Open Open
다섯번째 5의 배수 : 열려있으면 닫고 닫혀있으면 열린다
방번호 1 2 3 4 5 Open/Closed Open Closed Closed Open Closed
이렇게 해서 결과적으로 열려있는 방은 1번과 4번방 두개 이므로
결과값으로 2가 출력된다.
두번째 테스트 케이스인 10 같은 경우는
1~10번방까지 있고 1의배수부터 2의배수, 3의배수 . . . 9의배수, 10의 배수까지 진행되면 된다.
힌트를 얻었으면 직접 풀어보고 도저히 안풀리면 아래의 소스를 참고 하시길 바란다.
.
.
.
.
.
<소스 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 |
#include <stdio.h>
int T, n;
int main(){
for(scanf("%d", &T);T--;){
scanf("%d", &n);
int arr[101]={0};
int open = 0;
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j+=i)
arr[j] = !arr[j];
for(int i=1; i<=n; i++)
open += arr[i];
printf("%d\n", open);
}
} |
cs |
C언어 기반으로 짠 코드이다.
따로 scanf로 테스트케이스의 갯수를 받아서 처리하지않고
for문안에서 받아서 바로 처리하게 한다.
두번째 scanf는 5와 10 같은 테스트케이스를 받는 것이다.
open변수는 열려있는 방의 갯수를 쓰기 위해 선언하고 0으로 초기화했다.
문제상에서 5 <= n <=100 이라고 조건이 걸려있다.
5번방에서 100번방까지 존재한다는것!!
(여기서 굳이 오류처리는 해주지 않아도 된다.)
배열을 101까지 주어 0부터 100번까지 총 101개를 만들어준다.
C언어에서 0이 아닌 수는 전부 참true이다.
그래서 배열에 0으로 초기화를 해서 닫혀있음을 표현한다.
이중 for문으로 첫번째 for문은 1에서 n까지 한번씩 돌게하며
두번째 for문으로 각 해당하는 숫자의 배수만큼 돌게 한다.
그리고 해당하는 수는 각각의 값을 ! 을 붙여 0 이면 1, 1이면 0을 입력받게 한다.
!은 Not이라는 의미로
!true == false이고
!false == true이다
각 배수들이 for문으로 다 돌았다면 열려있으면 1, 닫혀있다면 0의 값을 가지고 있을 것이다.
다시 한 번 for문으로 배열을 하나하나씩보면서 Open 변수에 더해준다.
앞에 말했듯 열려있으면 1이므로 총 열려있는 방의 갯수를 알 수 있다.
마지막으로 Open의 변수값을 정수로 출력해준다.