[PyPy3] BOJ(백준) 17626번 - Four Squares

링크

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

난이도(solved.ac 참고)

실버5

풀이

input값 n을 받았을 때, 우선 9행에서 이 수가 특정 수의 제곱수인지 여부를 걸러낸다.

 

처음에는 무조건 그 수와 가장 가까운 제곱수를 찾아내 그 수를 더하고 남은 값을 DP 처리하는, 그리디 방식으로 생각했다.

근데 그렇게 하자니, 12라는 훌륭한 반례가 있다.

12
= 3^2 + 1^2 + 1^2 + 1^2  (총 4개)
= 2^2 + 2^2 + 2^2  (총 3개)

그 수와 가장 가까운 제곱수를 항상 더하는 방식으로 가져간다면 위의 12처럼 12와 가장 가까운 제곱수인 3을 가져갔을 때의 개수가 2를 세 개 가져갔을 때의 개수보다 더 많다. 그렇기 때문에 그리디와 같은 방식으로 풀면 풀 수가 없다.

 

그래서, 1부터 그 수와 가장 가까운 제곱수까지를 범위로 하는 반복문을 돌리면서 그 제곱수를 i에서 빼준 인덱스에 해당하는 DP값에 +1을 해주는 방식으로 작성했다.

위에 12를 예로 들어 보겠다. for문을 돌리면 결국 temp에 들어가는 값은

temp = [dp[12-1], dp[12-4], dp[12-9]] = [dp[11], dp[8], dp[3]] = [4, 2, 2]

가 된다. 이중에 가장 작은 값인 2가 dp[12]가 되는 것이다.

i가 2부터 시작하기 때문에 dp값이 시간이 지나면서 점차 쌓이게 된다.

 

실버 5라고 얕봤는데, 논리 생각해내기가 생각보다 시간이 꽤 걸렸다. 코드 시간 복잡도가 구려서 Python 3이 아니라 PyPy3으로 돌렸고, 맞긴 했으나 좋은 코드가 아니라는 생각이 들어 일단 다시 풀고 Python 3 버전으로도 업데이트 할 생각이다.

 

1699번 제곱수의 합과 같은 문제이다.