목록백준 1699번 (1)

하나씩 알아가기

[BOJ_1699] 제곱수의 합

입력 받은 수를 제곱수의 합으로 나타낼 때 각 항(반드시 양의 정수의 제곱)의 수의 최소값을 구하는 문제입니다. 수 1 2 3 4 5 6 7 8 ... 항의 개수 1 2 3 1 2 3 4 2 ... DP 테이블을 갱신시켜 나가는데 바깥 루프에서는 dp[i] = i 즉, 그 수 만큼의 값으로 채워주고 이것이 최댓값입니다. 안쪽 루프에서는 더 작은 횟수로 줄일 수 있을 때 갱신 해 나갑니다. dp[i] = min(dp[i], dp[i-j**2] + 1) 이것이 가장 핵심이 되는 구문인데 이 식을 생각해 내는것이 정말 어려운 것 같습니다. 여기서 +1을 해주는 이유는 어떤 수든지 최소 한 개의 항으로는 나타내야 하기 때문입니다. 즉 dp[x] = 0 은 불가능합니다. 1부터 시작합니다. n = int(inpu..
알고리즘 2021. 2. 1. 20:37
이전 Prev 1 Next 다음