[백준 - 1699] 제곱수의 합

#include <iostream>
#include <algorithm>
using namespace std;

int dp[100'001];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;

	dp[1] = 1;	dp[2] = 2;	dp[3] = 3;	dp[4] = 1;

	for (int i = 5; i <= n; ++i)
	{
		dp[i] = i;
		for (int j = 0; j *j <= i; ++j)
		{
			dp[i] = min(dp[i], dp[i - (j * j)] + 1);
		}
	}

	cout << dp[n];
	return 0;
}

---

||사고 과정

다른 사람의 풀이를 보고서야 해결했던 문제다

 

나는 처음에 어떠한 규칙이 있을거라고 생각했고 약간 많은 노가다와 억지로 규칙을 이끌었는데

예외가 있었다..

 

내가 잘못했던건 첫번째로 어떻게 해야 최소 개수를 구할 수 있는지 충분히 생각하지 않았다는 점,

물론 나올 수 있는 최대 제곱수를 이용 하긴 했지만 거기서 더 나아가지 못했다.

 

두번째로는 예외를 더 생각해보지 않았던 것

이거는 내가 항상 더 많이 주의해야겠다.

---

||사용 기법

• DP

---

||풀면서 느낀 것

• 응용

이 문제는 아주 유명한 문제인 최소개수로 동전 거슬러주기 와 비슷한데 동전은 잘 생각했으면서

이건 풀지 못한게 넘 속상하다

• 예외 생각

예외를 생각하기 넘 힘들어서 조금만 해보고 마는 경우가 있는데 앞으로는 일정 시간동안 생각해봐야겠다.