[백준알고리즘] - 13909번 창문 닫기_Java

백준 알고리즘 '약수, 배수와 소수2' 단계를 풀면서 최대 공약수, 최소 공배수 등 

약수와 배수의 기초 수학적인 알고리즘을 많이 익혔다.

그러다가, 간단하게 보이는 제목의 '창문 닫기'에서 이전에 배웠던 약수와 배수 방식으로 문제를 풀다가 난관에 봉착했다.

 

 

 

문제를 처음 읽고 N=5인 경우를 가정해서 창문의 열고 닫힘의 경과를 풀었을 때

n의 약수의 개수가 홀수인 경우 n번째 창문이 열려있고,

n의 약수의 개수가 짝수인 경우 n번째 창문이 닫혀있다는 규칙을 찾아냈다.

	1번 창문	2번 창문	3번 창문	4번 창문	5번 창문
초기 상태	0	0	0	0	0
1번째 사람	1	1	1	1	1
2번째 사람	1	0	1	0	1
3번째 사람	1	0	0	0	1
4번째 사람	1	0	0	1	1
5번째 사람	1	0	0	1	0

 

1번 창문과 4번 창문의 특징은 약수의 개수가 홀수이다. (1=1, 4=1,2,4)

그러므로 처음에 작성한 코드는 약수의 개수를 세고 하고, 홀수인 경우만 카운트하도록 작성했다.

약수의 개수를 모두 셀 필요는 없고 제곱근까지만 세어 반복수행시간을 줄였다.

import java.util.*;
public class Main{
    public static void main(String[] a) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int cnt = 0;
		
		for(int i=1; i<=n; i++) {
			if(getDivisorCnt(i)%2==1) {
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}
	
	public static int getDivisorCnt(int num) {
		int cnt = 1;
		
		for(int i=1; i<=Math.sqrt(num); i++) {
			if(num%i==0) cnt++;
		}
		return cnt;
	}
}

 

 

결과는 시간초과였다.

내 코드에서 더이상 수행시간을 줄일 순 없다는 생각이 들어서 좀 더 쉬운 패턴을 찾아보았다.

그렇게 찾은 것이 약수의 개수가 홀수인 경우 약수에 제곱근이 포함된다는 것이었다.

n번	약수	제곱근
1	1	1
4	1, 2, 4	2
9	1, 3	3
16	1, 4	4

 

 

그렇게 다음에 생각한 것은 제곱근이 정수로 떨어지는 경우를 카운트 할려고 했다.

쉽게 조건문을 짠다면 [Math.sqrt(n) * 10 % 10 == 0] 요런식으로 말이다.

정답이라고 생각하고 다른 사람들 코드를 확인하였는데 웬걸... 반복문 없이 훨씬 간단하게 작성되어 있었다.

 

import java.util.*;
public class Main{
    public static void main(String[] a) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		System.out.println((int)Math.sqrt(n));
	}
}

 

n번 제곱근의 정수형을 출력하는 형식으로 되어있기에 처음에는 이해가지 않았다.

어째서 제곱근을 가지는 정수를 카운트하지 않고도 n의 제곱근을 구하는 것으로 성립이 된다는 말인가 했다.

다른 블로그 글을 찾아봐도 n이하의 제곱근의 수 = n의 제곱근의 정수형 이라는 내용밖에 얻을 수 없었다.

그렇게 컴퓨터를 끄고 잠시 샤워를 하는 도중에 갑자기 이해가 되었다.

 

결국 제곱근이라는 것은 동일한 약수의 곱인것이다.

제곱근	제곱수
1	1
2	4
3	9
4	16
5	25

 

예를 들어, 10의 제곱근은 3.16227766017 이다. 그 이하의 정수형 제곱근 1, 2, 3이 존재한다는 것을 의미한다.

그렇기에 n의 제곱근의 정수형 = n이하의 제곱근 개수가 성립하는 것이다.

 

생각해보면 단순한 것을 나만 쉽게 이해하지 못한거 같았다.

다시한번 수학적 지식이 얼마나 코드를 쉽게 만들어주는지를 체감하면서...

오늘의 포스팅을 마친다.