BOJ-13909 창문 닫기 Swift

문제

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

마지막에 열려 있는 창문의 개수를 출력한다.

풀이

입력된 N의 제곱근을 정수로 변환해서 출력한다.

 

이 문제를 처음 봤을때, N의 최댓값이 21억인것을 보고, 배열과 for반복문을 이용하지 않고 단순히 계산으로 풀어야 한다는걸 알았다.

규칙을 찾는 중 n= 1 부터 4까지 했을때,

n = 1  정답: 1

• 1번 -> (1)

n = 2 일때 정답: 1

• 1번 ->  (1, 1)
• 2번 ->  (1, 0)

n = 3 일때 정답: 1

• 1번 -> (1, 1, 1)
• 2번 -> (1, 0, 1)
• 3번 -> (1, 0, 0)

n = 4 일때 정답: 2

• 1번 -> (1, 1, 1, 1)
• 2번 -> (1, 0, 1, 0)
• 3번 -> (1, 0, 0, 0)
• 4번 -> (1, 0, 0, 1)

여기까지 직접 찾았을땐, n의 제곱근이 정답일 줄 몰랐는데 n = 9 일때 창문의 수가 3개이고 ,예제 입력 중 24를 입력했을때 √24 = 4.xx 인데 4인걸 보고 알았다.

 

import Foundation

var num = Double(readLine()!)!

print(Int64(sqrt(num)))