[백준 13909] 창문 닫기 (python)

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

13909번: 창문 닫기

창문 닫기 문제

N 개의 창문이 있을 때, 1부터 시작해서 해당 수의 배수만큼 닫혀있으면(0)  열고(1), 열려있으면(1) 닫고(0)를 반복하고, 최종적으로 열려있는 창문의 개수를 확인하는 문제

수학적 접근으로 해결할 수 있었다.

📌 문제 접근 포인트

1. 조건을 몇 개 직접 구현해 보자. 주어진 숫자 N이 21억이란 숫자이므로, 단순 반복으론 해결할 수 없다.
2. 그렇다면 직접 경우의 수를 몇 개를 세어서 규칙성을 찾아보자.
3. 큰 수가 아닌 작은 수로 돌아가게 코드를 간단하게 작성 후, 결과 값을 확인해 보면
11122222333333344444444455555... 이렇게 결과를 얻을 수 있다.
이때, 값이 변화하는 지점인 1, 4, 9 , 16 ,25에 대해서 생각해 보면 각각 특정 숫자(1, 2, 3, 4, 5)의 제곱 수임을 알 수 있다.
4. 이를 얻을 수 있게 구현하면 된다.

반응형

⚙️ 내가 푼 정답코드 1

import sys
N = int(sys.stdin.readline())
result = 0
x = 1
while x*x <= N:
    x += 1
    result +=1
print(result)

⚙️ 내가 푼 정답코드 2

# 결국 N에 루트를 씌운 부분의 정수 부분만큼 열려있다.
print(int(input()**0.5))