▶실버2
풀이
ex) n = 12라면,
① dp[12 - 1*1] = dp[11], dp[12 - 2*2] = dp[8], dp[12 - 3*3] = dp[4] 중 가장 작은 값에 +1한 값이 dp[12]가 된다.
하지만 dp[1~11] 의 값을 알기 위해서는 1부터 1씩 증가하며 dp값을 구하는 작업을 먼저 진행한다.
i = 1) dp[1] = 1
i = 2) dp[2]: dp[2 - 1*1] + 1= dp[1] + 1 = 2
i = 3) dp[3]: dp[3 - 1*1] + 1 = dp[2] + 1 = 3
...
이런식으로 n까지 진행하는 과정에서, i 값에 따라 ①을 진행한다.
또, 주의할 점은 dp의 값을 dp값이 가질 수 있는 최대의 항의 수 개수로 초기화 해야한다. (dp[i] = i)
코드
#include <iostream>
#include <cmath>
#include <algorithm>
#include <typeinfo>
using namespace std;
int dp[100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
//최대의 항 개수를 dp값으로 초기화
dp[i] = i;
//i의 제곱근보다 작은 수를 차례로 탐색하며 최소 항 개수를 가지면 값 갱신
for (int j = 1; j <= int(sqrt(i)); j++) {
if (dp[i] > dp[i - j * j] + 1) {
dp[i] = dp[i - j * j] + 1;
}
}
}
cout << dp[n];
}
'Algorithm > Baekjoon' 카테고리의 다른 글
2156_포도주 시식 (0) | 2023.01.16 |
---|---|
9465_스티커 (1) | 2023.01.16 |
11660_구간 합 구하기 5 (0) | 2023.01.11 |
11055_가장 큰 증가 부분 수열 (0) | 2023.01.10 |
11057_오르막수 (0) | 2023.01.04 |