intro : 이런 문제들 너무나도 싫다.

백준 문제링크

문제

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

입력

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

출력

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

문제 풀이 (108ms)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 주어지는 입력값 
        int input = Integer.parseInt(br.readLine());
        // 제곱근의 값으로 결과값 계산
        int result = (int) Math.sqrt(input);
        
        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(String.valueOf(result));
        bw.flush();

        // 자원 반납
        bw.close();
        br.close();
    }
}

문제 해석

아, 이문제는 정말이지 푸는데 굉장히 오래걸렸다.(이전에도 말했지만 직관적이지 않은 문제, 정수론 같은 방법을 통해서 푸는 문제들은 난이도에 상관없이 항상 어렵다) 단순히 반복문을 통해서 1부터 주어진 N까지의 값만큼 반복문을 돌면서 열고 닫고를 체크하자니 주어지는 값의 N의 범위가 21억까지여서 시간복잡도만 단순히 따져보아도 이렇게 푸는 문제가 아니라고 느껴지니 다른 방법을 통해 문제를 풀어야겠다고 생각이 들었다.

잘 생각해보면 결국 내가 계산해야하는 결과값은 마지막에 열려 있는 창문의 개수 이다. 그렇다면 열려있는 창문은 언제 열려있는가? 주어지는 값이 5라고 생각해봤다.

그렇다면 다음과같이 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘) 값이 주어지고 순차적으로 1~5의 배수값들은 열고 닫고가 반복된다. 이내용을 다음과같이 순서대로 표현해보았다.

입력값 : 5 인 경우

초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘)

반복문 1: 1(열림),2(열림),3(열림),4(열림),5(열림)
반복문 2: 1(열림),2(닫힘),3(열림),4(닫힘),5(열림)
반복문 3: 1(열림),2(닫힘),3(닫힘),4(닫힘),5(열림)
반복문 4: 1(열림),2(닫힘),3(닫힘),4(열림),5(열림)
반복문 5: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘)

마지막에 열려있는 창문의 개수 : 2

대충 여기서 살짝 감이 왔던게 아 이거 약수와 연관이 있구나, 약수의 개수가 홀수인경우는 열려있고 짝수인 경우는 닫혀있다고 뭔가 느낌이 왔다, 여기서 한번 더 다른 케이스에 대해서 검증해 보았다.

입력값 : 9 인 경우

초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘),6(닫힘),7(닫힘),8(닫힘),9(닫힘)

반복문 1: 1(열림),2(열림),3(열림),4(열림),5(열림),6(열림),7(열림),8(열림),9(열림)
반복문 2: 1(열림),2(닫힘),3(열림),4(닫힘),5(열림),6(닫힘),7(열림),8(닫힘),9(열림)
반복문 3: 1(열림),2(닫힘),3(닫힘),4(닫힘),5(열림),6(열림),7(열림),8(닫힘),9(닫힘)
반복문 4: 1(열림),2(닫힘),3(닫힘),4(열림),5(열림),6(열림),7(열림),8(열림),9(닫힘)
반복문 5: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(열림),7(열림),8(열림),9(닫힘)
반복문 6: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(열림),8(열림),9(닫힘)
반복문 7: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(닫힘),8(열림),9(닫힘)
반복문 8: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(닫힘),8(닫힘),9(닫힘)
반복문 9: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘),6(닫힘),7(닫힘),8(닫힘),9(열림)

마지막에 열려있는 창문의 개수 : 3개

여기까지 손으로 그려보니 뭔가 순차적으로 그려보면 규칙이 나오지 않을까 싶어서 다음과 같이 순차적으로 그려보고 마지막에 열려있는 창문의 개수와 연관관계를 유추해보고자 하였다.

입력값 : 1 인 경우
초기상태: 1(닫힘)
반복문 1: 1(열림)
마지막에 열려있는 창문의 개수 : 1개

입력값 : 2 인 경우
초기상태: 1(닫힘),2(닫힘)
반복문 1: 1(열림),2(열림)
반복문 2: 1(열림),2(닫힘)
마지막에 열려있는 창문의 개수 : 1개

입력값 : 3 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘)
반복문 1: 1(열림),2(열림),(열림)
반복문 2: 1(열림),2(닫힘),(열림)
반복문 3: 1(열림),2(닫힘),(닫힘)
마지막에 열려있는 창문의 개수 : 1개

입력값 : 4 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘)
반복문 1: 1(열림),2(열림),(열림),(열림)
반복문 2: 1(열림),2(닫힘),(열림),(닫힘)
반복문 3: 1(열림),2(닫힘),(닫힘),(닫힘)
반복문 4: 1(열림),2(닫힘),(닫힘),(열림)
마지막에 열려있는 창문의 개수 : 2개

입력값 : 5 인 경우
초기상태: 1(닫힘),2(닫힘),3(닫힘),4(닫힘),5(닫힘)
반복문 1: 1(열림),2(열림),3(열림),4(열림),5(열림)
반복문 2: 1(열림),2(닫힘),3(열림),4(닫힘),5(열림)
반복문 3: 1(열림),2(닫힘),3(닫힘),4(닫힘),5(열림)
반복문 4: 1(열림),2(닫힘),3(닫힘),4(열림),5(열림)
반복문 5: 1(열림),2(닫힘),3(닫힘),4(열림),5(닫힘)
마지막에 열려있는 창문의 개수 : 2개

각 숫자의 약수의 개수가 짝수인 경우는 결론적으로 닫힌 창문이 되는데, 그 이유는 초기에 닫혀있던게 짝수번 2,4,6,8 만큼 열렸다 다시 닫히기 떄문에 결론적으로는 닫힌 창문이된다. 그렇다면 약수의 개수가 홀수인경우는 1,3,5,7,9 만큼 열리고 닫히고 다시 열리기 때문에 결론적으로는 열린 창문이 된다. 결론적으로 약수의 개수가 홀수인 경우만 창문이 열린다는걸 알 수 있다.

이걸 코드로 구현해보자면 주어지는 값 N의 제곱근의 값은 결론적으로 위 과정을 반복하였을때 열려있는 창문의 개수를 구할수 있는 공식이 된다는 걸 알 수 있다.