득이공간
[백준 C++] 17626 Four Squares - 다이나믹프로그래밍 본문
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
int DP[50001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
for (int i = 1; i <= N; ++i)
{
int MinCount = INT_MAX;
for (int j = 1; j <= sqrt(i); ++j)
{
int CurrentNumber = j * j;
if (CurrentNumber == i)
{
DP[i] = 1;
break;
}
int Count = DP[i - CurrentNumber] + 1;
if (Count < MinCount)
{
DP[i] = Count;
MinCount = Count;
}
}
}
cout << DP[N];
}
다이나믹 프로그래밍 & 브루트포스 알고리즘으로 푸는 문제입니다.
1, 4, 9, 16, ... 등의 제곱수들의 해는 1이고, 최종적으로는 N의 해의 최소값을 구해야 하기 때문에
N 보다 작은 제곱수 하나를 선택한 경우(1 + DP[N - 해당제곱수])들 중에서 가장 작은 값을 선택하도록 해야 합니다.
따라서 바텀-업 방식으로 1부터 N까지 i를 1씩 증가시켜서 DP 배열을 채워주는데
다음과 같은 방식을 사용합니다.
1. i가 제곱수인 경우, 해는 1
2. i가 제곱수가 아닌 경우, i 보다 작은 제곱수 중 하나를 선택한 경우들 중 최소값 선택
ex. i 가 15인 경우,
i 보다 작은 제곱수: { 1, 4, 9 }
위의 제곱수 중 하나를 선택한 각각의 경우: { DP[14] + 1, DP[11] + 1, DP[6] + 1 }
위의 세 개의 값 중에서 최소값이 i의 해가 됩니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 21736 헌내기는 친구가 필요해 - 너비우선탐색 (0) | 2024.02.16 |
---|---|
[백준 C++] 11279 최대 힙 - 우선순위큐 (0) | 2024.02.15 |
[백준 C++] 11727 2×n 타일링 2 - 다이나믹프로그래밍 (0) | 2024.02.15 |
[백준 C++] 9461 파도반 수열 - 다이나믹프로그래밍 (0) | 2024.02.15 |
[백준 C++] 9375 패션왕 신해빈 - 조합론 (0) | 2024.02.15 |