백준 13909번 풀이

문제

https://www.acmicpc.net/problem/13909

마지막에 열려있는 창문의 개수는 몇 개인가?

 

풀이

문제가 얼탱이없어서 뇌정지 오는 것에 비하면 풀이 진짜로 별거 없다. 수학책에서 소금물 농도 계산하던건 양반이여.

 

일단 이 문제, 입력이 3일떄 왜 1이냐... 일단 1번이 모든 창문을 열고 시작해서 그렇다. 2, 3까지는 다 공통적으로 1인데 2, 3번에 해당하는 사람이 자기 창문을 닫고 땡이거든. 그 뒤로 한 4, 5까지는 머릿속에서 계산이 되는데 6부터는 이제 암산으로 하기 빡세거든요? 그래서 내가 그려봤음.

여기까지만 보고 패턴을 찾는 분도 계실텐데, 일단 소수인 창문은 한 번 닫고 나면 안 열린다. 합성수의 경우 약수가 홀수개면 열리고, 약수가 짝수개면 최종적으로 닫힌다. 그래서 위 그림에서 4는 열고->닫고(2)->열고(4) 해서 최종적으로 열려있는 상태고, 6은 열고->닫고(2)->열고(3)->닫고(6) 해서 최종적으로 닫혀있는 상태. 이렇게 하면 열려있는 창문이 몇 개인지 쉽게 도출 가능하다.

 

그리고 잘 봐봐요. 1부터 3까지는 1이고, 4부터 8까지는 2고, 9부터 15까지는 3이고, 16부터 얼마까지인지는 모르지만 4잖아요. 숫자가 바뀌는 시발점이 1, 4, 9, 16이다. 이거 보고 뭐 오는 거 없어요? 없으시면 유튜브에 정승제 50일 수학 치고 루트편 보고 오십쇼. 어? 루트? 이거 설마? 그래요! 루트를 때려! 그거야!

 

자, 봐봐요. 루트는 제곱해서 n이 되는 수잖아요. 1의 제곱근은 1이고 4의 제곱근이 2면 루트 2, 루트 3은 얼마겠음? 아니 자세히는 몰라도 2, 3이 4보다 작으니까 루트 2, 루트 3은 2와 1 사이의 어딘가에 있을 거 아닙니까.

1.0 1.414 1.732 2.0

순서대로 루트 1, 루트 2, 루트 3, 루트 4다. 이제 감이 좀 오십니까? 그럼 5부터 9까지는요?

2.236 2.449 2.646 2.828 3.0

루트 4가 2고 루트 9가 3이니까 루트 5부터 루트 8까지는 다 2와 3 그 어딘가에 있을 거 아닙니까. 근데 쟤는 2잖아요. 아니 그니까 소수점을 떼야죠. ceil 말고 round 말고 floor 줘야지!

 

import sys
N = int(sys.stdin.readline().strip())

print(int(N ** 0.5))

그래서 이게 답이다. 1/2승 하면 제곱근임.