์ค๋ฒ5 : ๋์ ๊ณํ๋ฒ ๋ฌธ์ ์ด๋ค.
์๊ฐ
์๊ฐ ๋ณด๋ค ํ๋ค๊ฒ ํผ ๋ฌธ์ ์ด๋ค. n์ด 50000์ด๊ณ , ์๊ฐ ์ ํ์ด 0.5์ด์ด๊ธฐ ๋๋ฌธ์ ์์ ํ์์ผ๋ก ํ๋ฉด ํ๋ค ๊ฒ์ด๋ผ ์๊ฐํ๋ค. ๊ทธ๋์ ๋์ ๊ณํ๋ฒ ๋ฐฉ๋ฒ์ผ๋ก ํ์ด๋ฅผ ์ฑํํ๋ค.
์ด ๋ฌธ์ ๋ ๋์ ๋ฌธ์ ์ ๋น์ทํ๊ฒ ์๊ฐํด์ผ ํ๋ค. ๊ฒฐ๊ตญ ๋ช๊ฐ์ ์ ๊ณฑ์๊ฐ ์ต์๋ก ํ์ํ๋๋ ๋ฌธ์ ์ธ๋ฐ, ์ฌ์ค 1๋ก ๋ชจ๋ ์๋ฅผ ๋ง๋ค ์ ์๊ธฐ ๋๋ฌธ์ ๋ํด์ง๋ ์ซ์์ ๊ฐ์๊ฐ ๋์ด๋จ์ ๋ฐ๋ผ ์ต์ ๊ฐ์๋ก ์ ๋ฐ์ดํธ๋ฅผ ํด์ฃผ๋ ๊ฒ์ด ๋ง๋ค.
์ ์
dp[i]
= i์ ๋ง๋๋๋ฐ ์์ด ํ์ํ ์ต์ ์ซ์์ ๊ฐฏ์
์ ์๋ 1์ฐจ์ ๋ค์ด๋๋ฏน์ด์ง๋ง, ๊ณ์ ์
๋ฐ์ดํธ๋ฅผ ํด์ฃผ์ด์ผ ํ๋ค. ์
๋ฐ์ดํธ๋ฅผ ํ๊ฒ ๋๋ฉด ์ต์ข
์ ์ผ๋ก 4๋ฒํ๋ฉด i์ ๋ง๋๋๋ฐ ์์ด ํ์ํ ์ต์ ์ ๊ณฑ์์ ๊ฐฏ์
๋ก ์ ๋ฆฌ๋ ์ ์๋ค. (๋ฌธ์ ์ ์ด๋ฏธ ์ฆ๋ช
๋์๋ค๊ณ ํ๋ค)
์ ํ์
dp[i] = min(dp[i], dp[j*j]+dp[i-j*j])
์ ์๊ฐํด๋ณด์. n์ด๋ผ๋ ์ซ์๋ฅผ ๋ง๋ค๊ธฐ ์ํด ํ์ํ ๊ฐ์๋ dp[n-i*i]
๋ก ๋ถํฐ ์ฌ ์ ๋ฐ์ ์๋ค. ์ ๊ณฑ์๋ฅผ ๋ํ์ฌ ํด๋น ์๊ฐ ๋ง๋ค์ด์ง๊ธฐ ๋๋ฌธ์ด๋ค.
n = n-1*1 + 1*1
= n-2*2 + 2*2
= n-3*3 + 3*3
...
= n-sqrt(n)*sqrt(n) + sqrt(n)*sqrt(n)
๊ทธ๋ ๋ค๋ฉด, dp์ญ์ ์ด ๊ด๊ณ๊ฐ ์ ์ฉ๋๋ ์๊ฐํด๋ณด์. 9์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์๋ฅผ ๋ง๋ค๊ธฐ ์ํด์๋ (8์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์ + 1์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์) ๊ทธ๋ฆฌ๊ณ (5์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์ + 4์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์), (3์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์ + 0์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์)๋ฅผ ๋น๊ตํ๋ฉด ๋๋ค. ์ด ๋ ๋ค์์ ๋ฐ์ํ๋ ์ต์ ๊ฐ์(1, 4, 0)์ ๋ชจ๋ ์ ๊ณฑ์ ์ด๋ค. ํ์ง๋ง ์์ ์ ๊ณฑ์๊ฐ ์๋๊ธฐ ๋๋ฌธ์ 1๋ณด๋ค ํฐ ์ซ์๋ฅผ ๊ฐ์ง๊ณ ์์ ๊ฒ์ด๋ค. ํ์ง๋ง ์
๋ฐ์ดํธ ํ๋ ๊ณผ์ ์์ ๊ณ์ํด์ ์ซ์๊ฐ ์์์ง๊ณ , ์ด๊ฒ์ ๋ฌธ์ ์์ ์ฆ๋ช
๋ ์ฌ์ค๊ณผ ๊ฐ์ด 4๋ฅผ ์ด๊ณผํ ์ ์๋ค. ์ค๋ช
์ด ๋๋ฌด ์ด๋ ต๋ค
||0|1|2|3|4|5|6|7|8|9| |::|:|:|:|:|:|:|:|:|:|:| |1|0|1|2|3|1|5|6|7|8|1| |2|0|1|2|3|1|2|3|4|2|1| |3|0|1|2|3|1|2|3|0|0|1| |4|0|1|2|3|1|2|3|0|0|1|
1์ ํ๋ฒ์ ์ ๊ณฑ์๊น์ง ์ฌ์ฉํ์ ๋ ํํํ ์ ์๋์ง๋ฅผ ๋ํ๋ธ ๊ฒ์ด๋ค. 5๋ ์ ๊ณฑ์๊ฐ ์๋๋ฏ๋ก ์ด๊ธฐ๊ฐ์ INF๋ก ์ก๋๋ค. ๊ทธ ๋ค์์ผ๋ก 2๊ฐ์ ์ซ์๊น์ง ์ฌ์ฉํ์ ๋ ํ์ํ ๊ฐ์๋ฅผ ์๊ฐํด๋ณด์. (1, 4), (2, 3)์์ ์ฌ ์ ์๋๋ฐ, dp๊ฐ์ ๋ํ์ ๋ ์ต์๊ฐ์ด 2์ด๋ฏ๋ก 5๋ 2๊ฐ์ ์ ๊ณฑ์๋ฅผ ์ฌ์ฉํ์ ๋ 2๊ฐ๋ฅผ ๋ํ๋ฉด ๋ง๋ค์ด์ง๋ค. ์ด๋ ๊ฒ ๋ชจ๋๋ฅผ ์ ๋ฐ์ดํธ ํ๋ฉด, 2๊ฐ์ ์ซ์๋ฅผ ์ฌ์ฉํ์ ๋ ํ์ํ ์ ๊ณฑ์์ ์ต์๊ฐ์๋ฅผ ์ ๋ฐ์ดํธ ํ ์ ์๋ค. 3๊ฐ์ ์ซ์๊น์ง ์ฌ์ฉํ๋ค๋ฉด, ์ฌ์ ํ ๋ฐฉ๋ฒ์ ๋๊ฐ๋ค. ํ์ง๋ง ์ด๋ฏธ dp์ ์๋ ๊ฐ์ ๊ทธ ์ซ์๋ฅผ ํํํ๊ธฐ ์ํด ํ์ํ ์ต์ ์ซ์์ ๊ฐ์๋ฅผ ๋๋ณํ๊ณ ์๋ค. ๋ฐ๋ผ์ ์ ๋ฐ์ดํธ๋ฅผ ํ๋ฉด ์๋์ ์ผ๋ก ์ต์ ๊ฐ์๋ก ์ ๋ฐ์ดํธ ๋๋ค. ์ฌ๊ธฐ์ ํต์ฌ์ m๊ฐ์ ์ซ์๊น์ง๋ฅผ ์ฌ์ฉํ์ ๋ ์ต์์ซ์์ ๊ฐ์๋ผ๋ ๊ฒ์ด๋ค. ์ฆ ์ด ๋ฐฉํฅ์ผ๋ก๋ dp์ ์ ์๊ฐ ์ ์ฉ๋๊ณ ์๋ค. ๋ง์ฐฌ๊ฐ์ง๋ก 4๋ฒ์งธ ์ซ์๊น์ง ์ฌ์ฉํ์๋ ์ ๋ฐ์ดํธ๋ฅผ ์งํํ๋ฉด ๋ต์ด๋ค.
Code
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 1e9;
int N;
int dp[50001];
int main(){
cin >> N;
fill(dp, dp+N+1, INF);
for (int i = 1; i <= N; i++) {
if (int(sqrt(i))*int(sqrt(i)) == i) dp[i] = 1;
else dp[i] = i;
}
for (int k = 0; k < 3; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= int(sqrt(i)); j++) {
dp[i] = min(dp[i], dp[j*j]+dp[i-j*j]);
}
}
}
cout << dp[N] << '\n';
}
//
// main.cpp
// test
//
// Created by ์ต์์ on 2021/03/15.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 1e9;
int main(){
int n;
int dp[50001];
cin >> n;
fill(dp, dp+n+1, INF);
int i = 1;
while(true) {
if (i*i > 50000) {
break;
}
dp[i*i] = 1;
i++;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= int(sqrt(i)); j++) {
dp[i] = min(dp[i], dp[i-j*j] + dp[j*j]);
}
}
cout << dp[n] << endl;
return 0;
}
Reference
๋ฐฑ์ค(17626๋ฒ) - Four Squares{: target=โ_blankโ}