백준 13909 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

시간제한과 메모리 제한 입력값을 보았을 때, 정석적으로 반복문을 사용하여 푸는 문제는 절대로 아닐 것 같다고 생각했다.

 

솔직히 동적 계획법이 떠올랐지만, 해당 섹터가 아니라 그 풀이에 대해서는 보류했다.

 

이런 식으로 문제에 접근하는 건 좋지 않다.

 

근데 동적계획법으로 했어도 풀 수 있을지는 모르겠다.

 

보통 이런 문제는 패턴이 있더라.

 

1부터 단순반복하며 패턴을 찾았다.

 

입력값과 출력값 순서대로 나열해보겠다. ex) 1, 1

1, 1

2, 1

3, 1

4, 2

5, 2

6, 2

7, 2

8, 2

9, 3

10, 3

...

 

출력값이 변하게 되는 부분이 1, 4, 9으로 1~의 제곱수마다 1씩 증가하는 것을 알 수 있다.

 

이를 근거로 코드를 짜보자.

print(int(int(input())**(1/2)))

문제해결