간단하지만 재미있는 약수의 성질(백준 13909번 : 창문닫기)

오늘은 실버 5단계인 백준 13909번 창문닫기 리뷰입니다.(문제 해결법을 깨닫고 재밌어서 바로 글남김)

 

문제를 요약하자면, N번째 사람은 N의 배수인 창문을 닫거나 열어서 마지막에 몇 개의 창문이 열려있는지 맞히는 문제

문제 해결을 위해 7번째 사람까지 메모장에 작성해 보며 찾은 규칙성은 N의 약수의 개수가 짝수면 창문이 열리고 홀수면 닫히는 것이다.

 

그래서 작성한 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Number_13909 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int windowCount = 0;
		for(int i = 1 ; i <= N ; i++) {
			// 약수의 개수가 짝수이면 창문이 닫힌 상태
			if(getDivisorCount(i) % 2 != 0) {
				windowCount++;
			}
		}
		bw.write(String.valueOf(windowCount));
		br.close();
		bw.flush();
		bw.close();
	}
	
	public static int getDivisorCount(int a) {
		int count = 0;
		for(int i = 1 ; i <= Math.sqrt(a) ; i++) {
			if(a % i == 0) count++;
		}
		
		if(Math.sqrt(a) * 10 % 10 == 0) {
			return count * 2 - 1;
		}else{
			return count * 2;
		}
	}
}

 

어제 바로 유튜브로 시간 복잡도를 공부했는데, 딱 봐도 이중 루프라서 시간제한이 2초정도는 되야 할거 같았는데 주어진 것은 1초였다. 결과는 바로

 

시간 제한이 1초인 것을 보고 약수의 개수를 찾아 푸는 문제는 아니라고 생각했다.

그래서 N을 9 정도까지 메모장에 작성하다가 깨달은 점은 특정 숫자에만 약수의 개수가 홀수라는 사실을 깨달았다.

1, 4, 9 

맞다. 바로 제곱근들이다. 실제로 문제 예시를 24로 한 것도 25를 염두에 두고 예시로 준 것이 아닌가 생각했다.

그래서 N이 제곱근일 때만 창문이 열리고 그 외에는 다 닫힌다.

 

사실 getDivisorCount를 만들 때 제곱근이냐 아니냐에 따라 약수의 개수를 -1을 해줬는데 더 효율적인 방법이 있었던 것이다. 아무튼 그래서 완성된 코드는 아래와 같다. (여기까지 해놓고 For문으로 제곱근을 일일이 찾은 내가 레전드)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Number_13909 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		bw.write(String.valueOf((int) Math.sqrt(N)));
		br.close();
		bw.flush();
		bw.close();
	}
}

 

재밌었다.