백준 1699 - 제곱수의 합 [DP]

스마일게이트 서버개발캠프도 어느덧 끝이 보인다.

이제 개발은 마무리 단계고 

최종 결과 문서만 완료하면 정말 끝난다.

 

팀원들과 사당 스터디룸에서 미팅을 마치고

'복돈이'에서 부추 삼겹살 회식 후 

소화 겸 푸는 알고리즘 문제

 

이번 문제에서도 역시나 한번에 통과하지 못했다...

첫 점화식을 잘못 세웠었는데

안일하게 가장 큰 제곱수(j*j)를 뺀 DP[i-j] + 1 이 DP[i]가 될 줄 알았는데

생각해보니 그렇게되면 12를 만들때 3이 아닌 4가 나오는 반례가 생긴다.

따라서 모든 경우의 수를 확인해 최소인 값이 DP[i]가 되는 구조로 바꾸니 정답

 

점화식을 세울 때 좀 더 생각해보고 코드를 짜는 버릇을 들여야겠다.