본문 바로가기
Beakjoon&프로그래머스/파이썬

[백준/파이썬]17626번 Four Squares

by 현장 2021. 8. 3.

-코드

n = int(input())
dp = [0, 1]
for i in range(2, n + 1):
    j = 1
    MIN = 50000
    while j ** 2 <= i:
        MIN = min(MIN, dp[i - j ** 2])
        j += 1
    dp.append(MIN + 1)
print(dp[n])

처음에 최대 4까지만 나오는 것을 모르고 풀다가 안 풀려서 보니 최대 출력 값이 4여서 틀리고 그 후 dp를 몰라서 dp를 여러 문제를 풀고 와서 보니 풀다가 일정한 패턴을 알아야 넘어가는데 for문 다음으로 넘어가는데 몰라서 패턴을 찾아보니 해결하였으나 패턴을 찾는 실력이 부족해서 좀 더 많이 풀어서 익숙해질 필요성을 깨달았습니다. 그리고 dp로 해결을 하면 파이썬으로 시간 초과가 나서 pypy3로 제출하였습니다.