๋ฌธ์ ๋ ์ฌ๊ธฐ
์ค๋ช
์คํ์ ์ ํํ๊ฒ N ํฌ๋ก๊ทธ๋จ
์ ๋ฐฐ๋ฌํด์ผ ํ๊ณ , 3kg
๊ณผ 5kg
๋ด์ง๊ฐ ์๋ค. ์ด๋ ์ต๋ํ ์ ์ ๊ฐฏ์์ ๋ด์ง๋ฅผ ๊ฐ์ ธ๊ฐ๋ฉฐ, 3kg์ 5kg ๋ด์ง๋ก ๊ฐ์ ธ๊ฐ ์ ์์ ๋์ -1์ ์ถ๋ ฅํ๋ค.
์๊ณ ๋ฆฌ์ฆ
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ์ฌ์ฉํฉ๋๋ค. ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ด๋, ์ฌ๊ทํธ์ถ ๋ฑ์ ์ด์ฉํด ํ๋ํ๋ ๊ณ์ฐํด๋๊ฐ ์ ์๋ ๋ฌธ์ ๋ฅผ ํจ์จ์ ์ผ๋ก(=๋น ๋ฅด๊ฒ) ํ๊ธฐ ์ํด ๊ณ ์๋ ํ๋ก๊ทธ๋๋ฐ ๊ธฐ๋ฒ์
๋๋ค.
cache๋ก ์ฌ์ฉ๋ ๋ฐฐ์ด์ ๋ง๋ ํ, ์์์๋ถํฐ ๊ตฌํ๊ณ ์ ํ๋ ๊ฐ๊น์ง ๋ฐฐ์ด์ ์ฑ์๋๊ฐ๋๋ค. ์ด๋ ์์์ ๊ตฌํ ๊ฐ์ ์ฌ์ฉํ์ฌ, ์ ํ์์ ๋ชจ์์๋ก ์ดํ์ ๊ฐ๋ค์ ์ฑ์๋๊ฐ๊ฒ ๋ฉ๋๋ค.
์ฆ ํน์ ๊ฐ๋ค์ ๋ํ์ฌ ์ผ๋ฐํ๊ฐ ๊ฐ๋ฅํ ์ ํ์์ด ์ ์ฉ๋๋ ๊ฒฝ์ฐ์ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
์ ์ฌ์ฉํ๋ฉด ๋ฉ๋๋ค.
ํด๋น ๋ฌธ์ ์ ๊ฒฝ์ฐ์๋, ๋์ถํด๋ณผ ์ ์๋ ์ผ๋ฐํ๋ ์ ํ์์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- DP[i] = min(DP[i-3]+1, DP[i-5]+1) => ๋จ, DP[i-3]๊ณผ DP[i-5]๊ฐ -1์ด ์๋๋ค.
- DP[i-3]๊ณผ DP[i-5]๊ฐ ๋ชจ๋ -1์ธ ๊ฒฝ์ฐ์๋, DP[i] ์ญ์ -1๊ฐ ๋ฉ๋๋ค.
์ด๋ฅผ ๊ตฌํ๊ธฐ ์ํด ์ฐจ๊ทผ์ฐจ๊ทผ DP[3]๋ถํฐ ๊ตฌํ๋, -1๊ฐ ์๋ ๊ฐ๋ค๋ง์ ์ถ๋ ค๋ณด๋ฉด
DP[3] = 1
DP[5] = 1
DP[6] = 2 = DP[6-3]+1
DP[8] = 2 = min(DP[8-3]+1, DP[8-5]+1)
DP[9] = 3 = DP[9-3]+1
DP[10] = 2 = DP[10-5]+1
DP[11] = 3 = min(DP[11-5]+1, DP[11-3]+1)
์์ฒ๋ผ ์ผ์ ํ ๊ท์น์ ๊ฐ๊ณ ์์์ ์ ์ ์์ต๋๋ค.
์ฝ๋
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int DP[5001];
int makeN(int sugar)
{
memset(DP, 0, sizeof(DP));
DP[3] = DP[5] = 1;
for (int i = 6; i <= sugar; i++)
{
if (DP[i - 3] && DP[i - 5]) DP[i] = min(DP[i - 3] + 1, DP[i - 5] + 1);
else if (DP[i - 3] && !DP[i - 5]) DP[i] = DP[i - 3]+1;
else if (!DP[i - 3] && DP[i - 5]) DP[i] = DP[i - 5]+1;
else DP[i] = 0;
}
if (DP[sugar] == 0) DP[sugar] = -1;
return DP[sugar];
}
int main()
{
int s;
cin >> s;
cout << makeN(s);
}