CodeDrive

문제:

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

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

입력:

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

출력:

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

풀이방법:

다이나믹 프로그래밍으로 풀어야 한다고 하는데 방의 개수가 100으로 작은편이기 때문에 완전탐색을 사용해서 풀었다.

0이면 열려 있고, 1이면 닫혀 있다고 했을 때, 해당하는 숫자 j의 배수마다 0이면 1로, 1이면 0으로 바꾸도록 했다. 이렇게 모두 탐색을 완료하면 0의 갯수에서 하나를 빼서 답을 구한다.

(다 풀고나니 1을 열려 있고, 0을 닫혀 있다 가정하고, 마지막에 sum을 하는 것이 더 깔끔할 것 같다.)

문제링크:

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