★★☆☆☆
접근 방식은 간단하고, 코드 짜는 것도 어렵지 않았다.
가장 처음에 n에 가장 가까운 제곱수와 나머지의 합으로 표현했다가 오답 처리가 되었다.
(11=dp[3]+dp[2])
알고보니, 12의 경우, 9+1+1+1 의 4항으로 표현하는 것보다
4+4+4의 3항으로 표현 가능한 경우가 있다는 것을 알았다.
<나의 풀이>
그래서 기본 개념은 동일하지만, 기존에는 for문을 1개만 사용하여
가장 가까운 제곱수의 값을 활용했던 부분을
n보다 작은 제곱수들의 값을 하나씩 대입하여 최솟값을 구하는 코드로 수정했다.
간단하게 제곱수를 구하고 루트값을 활용하기 위해
cmath 라이브러리의 pow 함수(제곱함수)와 sqrt 함수(제곱근함수)를 사용했다.
제곱수의 경우에는 1을 넣고 넘어가도록 했다.
<다른 사람의 풀이>
나처럼 pow 함수와 sqrt함수를 사용하지 않고,
오로지 i와 j로만 식을 구성했다.
함수에 여러번 접근할 필요가 없으므로 시간이 더 적게 걸린다는 장점이 있다.
dp[i]=min(dp[i],1+dp[i-jj] )
내가 참고했던 코드에서는 제곱수의 경우 따로 처리해주는 부분이 없었는데,
숫자가 커진다면 이를 처리하는 데 오랜 시간이 걸릴 것으로 보인다.
https://github.com/jeongopo/DaliyCodeCpp/commit/075b3d2b08e8f7f6ec35f3863e33ae27236f7085
일단 시작하기