백준 15736번 파이썬 문제풀이(청기 백기)

 

---

이 문제 완탐 돌리면 당연히 시간초과이다. 따라서 식을 찾아야하는데 몇번 해보면 1~3 = 1 , 4~8 = 2 , 9 ~ 15 = 3 , 16 ~ 24 = 4 와 같은 공식을 찾을 수 있다. 즉, N을 루트를 씌우고 int를 할 경우 똑같은 정수가 되는 구간이다. 하지만 나는 이러한 수학식을 빨리 찾지 못해 이 자체를 반복문을 구현 했다. 어찌어찌 pypy3로는 통과가 되긴 했다..

 

1. 정답

import math

N = int(input())

print(int(math.sqrt(N)))

 

2. 위 식을 완탐으로 찾기..

N = int(input())
count = 1

i = 3
index = 0
while True:

    for j in range(1, i + 1):
        index += 1

    if index >= N:
        break

    i += 2
    count += 1

print(count)