백준 13909: 창문 닫기(java, python)

문제

---

풀이

 

모든 창문이 닫힌 상태에서 시작한다는 것이 포인트이다. 창문이 마지막까지 열려 있으려면 창문의 상태를 바꿀 수 있는 사람이 홀수 명이어야 하므로, k번째 창문에 대해 k의 약수가 홀수 개이면 열려 있게 되고, 짝수 개이면 닫힌 채로 끝나게 된다. 따라서 n개의 창문이 주어졌을 때, n 이하의 약수가 홀수 개인 수의 개수를 구하면 해결된다.

 

어떤 수의 약수가 홀수 개이려면 그 수가 완전제곱수여야 한다.

k의 약수들은 곱해서 k가 되는 쌍끼리 짝을 이루므로, k의 약수 개수가 홀수이려면 k가 완전제곱수여야 하는 것이다.

 

따라서 N 이하 완전제곱수의 개수가 정답이 된다.

 

1. java

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		
		int N=scanner.nextInt();
		
		int count=1;
	
		while(count*count<=N) {
			count++;
		}
		
		System.out.println(count-1);
	}
}

 

2. python

import math

N = int(input())

result = int(math.sqrt(N))

print(result)