Dynamic Programming
ํฐ ๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋ก ๋๋ ์ ํธ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
Overlapping Subproblem (๊ฒน์น๋ ๋ถ๋ถ๋ฌธ์ )
Optimal Substructure(๋ฌธ์ ์ ์ ๋ต์ ์์ ๋ถ๋ถ์์ ์ ์ ์์ ๋) : ์์ ๋ฌธ์ ์์ ๊ตฌํ ์ ๋ต์ ๊ทธ๊ฒ์ ํฌํจํ๋ ํฐ ๋ฌธ์ ์์๋ ๋์ผํ๋ค.
์ด ๋๊ฐ์ง ์์ฑ์ ๋ง์กฑํด์ผ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ ์ ์๋ค.
Overlapping Subproblem
๋ฌธ์ : N๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
์์๋ฌธ์ : N-1๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ , N-2๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
๋ฌธ์ : N-1๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
์์๋ฌธ์ : N-2๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ , N-3๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
๋ฌธ์ : N-2๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
์์๋ฌธ์ : N-3๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ , N-3๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
์์ ๋ฌธ์ ๊ฐ ๊ฒน์ณ์ผํ๋ค. ํฐ ๋ฌธ์ ์ ์์ ๋ฌธ์ ๋ ์๋์ ์ด๋ค.
ํฐ ๋ฌธ์ ์ ์์ ๋ฌธ์ ๋ฅผ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ํ ์ ์๋ค.
๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋ก ์ชผ๊ฐค ์ ์๋ค.
Optimal Substructure
๋ฌธ์ ์ ์ ๋ต์ ์์ ๋ฌธ์ ์ ์ ๋ต์์ ๊ตฌํ ์ ์๋ค.
N-1๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ = N-2๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ + N-3๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
๊ฐ ๋ฌธ์ ๋ ํ๋ฒ๋ง ํ์ด์ผ ํ๋ค.
๊ฐ์ ๋ฌธ์ ๋ ๊ตฌํ ๋๋ง๋ค ์ ๋ต์ด ๊ฐ๋ค.(Optimal Substructure)
์ ๋ต์ ๊ตฌํ์ผ๋ฉด, ์ ๋ต์ ์ด๋๊ฐ์ ๋ฉ๋ชจํด๋๋๋ค.(๋ฐฐ์ด)=>Memoization
Top-down
๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋ก ๋๋๋ค.
์์ ๋ฌธ์ ๋ฅผ ํผ๋ค.
์์ ๋ฌธ์ ๋ฅผ ํ์์ผ๋, ์ด์ ๋ฌธ์ ๋ฅผ ํผ๋ค.
์ฌ๊ทํธ์ถ์ ์ด์ฉํด์ ๋ฌธ์ ๋ฅผ ์ฝ๊ฒ ํ ์ ์๋ค. ์๊ฐ๋ณต์ก๋๋ ์ฑ์์ผํ๋ ์นธ์ ์ X ํ ์นธ์ ์ฑ์ฐ๋ ๋ณต์ก๋(ํจ์ํ๋์ ์๊ฐ ๋ณต์ก๋)์ด๋ค.
// cpp
int memo[100]; //memoization
int fibonacci(int n){
if(n<=1){
return n;
}else{
if(memo[n]>0){
return memo[n];
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
return memo[n];
}
}
# python
# memorization
d = [0] * 100
def fibonacci_recursion(x):
# 1 or 2 ๋ 1
if x == 1 or x == 2:
return 1
# ์ด๋ฏธ ํ๋ฒ ํธ์ถ๋ ์ ์๋ ๊ฐ์ ๊ธฐ์ตํด๋ ๊ฐ ๋ฐํ
if d[x]!=0:
return d[x]
# ํ๋ฒ๋ ํธ์ถ๋์ ์๋ ๊ฐ์ ์ถ๊ฐ
d[x] = fibonacci_recursion(x-1) + fibonacci_recursion(x-2)
return d[x]
print(fibonacci_recursion(6))
Bottom-up
๋ฌธ์ ๋ฅผ ํฌ๊ธฐ๊ฐ ์์ ๋ฌธ์ ๋ถํฐ ์ฐจ๋ก๋๋ก ํผ๋ค.
๋ฌธ์ ์ ํฌ๊ธฐ๋ฅผ ์กฐ๊ธ์ฉ ํฌ๊ฒ ๋ง๋ค๋ฉด์ ๋ฌธ์ ๋ฅผ ํผ๋ค.
์์ ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์๊ธฐ ๋๋ฌธ์, ํฐ ๋ฌธ์ ๋ ํญ์ ํ ์ ์๋ค.
int d[100];
int fibonacci(int n){
d[0]=1;
d[1]=1;
for(int i=2;i<=n;i++){
d[i]=d[i-1]+d[i-2];
}
return d[n];
}
# bottom-up
# dp table
d = [0] * 100
def fibonacci_loop(n):
d[1] = 1
d[2] = 1
for i in range(3,n+1):
d[i] = d[i-1]+d[i-2]
print(d[n])
fibonacci_loop(99)
memoization์ ํ ๋ ๋ฌด์์ ๊ธฐ๋กํด์ผํ ์ง ์ ์ํ๋ ๊ฒ์ด ์ต์ฐ์ ์ด๋ค.
Top-down(memorization) ๋ฐฉ์์ 'ํํฅ์'์ด๋ผ๊ณ ๋ ํ๋ฉฐ, bottom-up ๋ฐฉ์์ '์ํฅ์'์ด๋ผ๊ณ ๋ ํ๋ค. DP์ ์ ํ์ ์ธ ํํ๋ bottom-up ๋ฐฉ์์ด๋ค.
Bottom-up ๋ฐฉ์์์ ์ฌ์ฉ๋๋ ๊ฒฐ๊ณผ ์ ์ฅ์ฉ ๋ฆฌ์คํธ(๋ฐฐ์ด)๋ DP ํ ์ด๋ธ ์ด๋ผ ๋ถ๋ฅด๋ฉฐ, memorization์ Top-down ๋ฐฉ์์ ๊ตญํ๋์ด ์ฌ์ฉ๋๋ ํํ์ด๋ค.
์ค์ต
1๋ก ๋ง๋ค๊ธฐ
D[N] = N์ 1๋ก ๋ง๋๋๋ฐ ํ์ํ ์ฐ์ฐ์ ์ต์๊ฐ 1. N์ด 3์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ฉด, 3์ผ๋ก ๋๋๋ค. D[N/3]+1
2. N์ด 2๋ก ๋๋์ด ๋จ์ด์ง๋ฉด, 2๋ก ๋๋๋ค. D[N/2]+1
3. 1์ ๋บ๋ค. D[N-1]+1
=> D[N]=min(1,2,3)
top-down
#include <iostream>
//Top-Down(์ฌ๊ท)
int d[1000001];
int divn(int n){
if(n==1) return 0;
if(d[n]>0) return d[n];
//-1
d[n]=divn(n-1)+1;
if(n%2==0){
int temp=divn(n/2)+1;
if(d[n]>temp) d[n] = temp;
}
if(n%3==0){
int temp=divn(n/3)+1;
if(d[n]>temp) d[n] = temp;
}
return d[n];
}
bottom-up
//Bottom-up
void divbu(int n){
d[1]=0;
for(int i=2;i<=n;i++){
d[i]=d[i-1]+1;
if(i%2==0 && d[i]>d[i/2]+1){
d[i]=d[i/2]+1;
}
if(i%3==0 && d[i]>d[i/3]+1){
d[i]=d[i/3]+1;
}
}
printf("%d",d[n]);
}
2Xn ํ์ผ๋ง
2Xn ์ง์ฌ๊ฐํ์ 1x2,2x1ํ์ผ๋ก ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์ => D[n]=2xi์ง์ฌ๊ฐํ์ ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์ => D[n]=D[n-1]+D[n-2]
์ด ๋, n=0์ผ ๋๋ ๊ฒฝ์ฐ์ ์์ด๊ธฐ ๋๋ฌธ์ 1์ ์ถ๋ ฅํ๋ค.
bottom-up
#include <iostream>
using namespace std;
int d[10001];
int main() {
int x;
cin >> x;
d[1]=1;
d[0]=1;
for(int i=2;i<=x;i++){
d[i]=d[i-1]+d[i-2];
d[i]%=10007;
}
cout << d[x] << "\n";
}
2xn ํ์ผ๋ง 2
2Xn ์ง์ฌ๊ฐํ์ 1x2,2x1,2x2ํ์ผ๋ก ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์ => D[n]=2xi์ง์ฌ๊ฐํ์ ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์ => D[n]=D[n-1]+2*D[n-2]
bottom-up
#include <iostream>
using namespace std;
int d[10001];
int main() {
int x;
cin >> x;
d[1]=1;
d[0]=1;
for(int i=2;i<=x;i++){
d[i]=d[i-1]+2*d[i-2];
d[i]%=10007;
}
cout << d[x] << "\n";
}
1,2,3 ๋ํ๊ธฐ
์ ์ n์ 1,2,3์ ์กฐํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ => D[n]=์ ์ n์ 1,2,3์ ์กฐํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์ => ๋ง์ง๋ง์ ์ค๋ ์๊ฐ ์ค์ํ๋ค. => D[n]=D[n-1]+D[n-2]+D[n-3]
bottom-up
#include <iostream>
using namespace std;
int d[10001];
int main() {
int t;
cin >> t;
while(t--){
int x;
cin >> x;
d[1]=1;
d[0]=1;
d[2]=2;
for(int i=2;i<=x;i++){
d[i]=d[i-1]+d[i-2]+d[i-3];
}
cout << d[x] << "\n";
}
}
๋ถ์ด๋นต ํ๋งคํ๊ธฐ
๋ถ์ด๋นต i๊ฐ๋ฅผ ํ์์ ์ป์ ์ ์๋ ์์ต P[i]์ผ ๋, N๊ฐ๋ฅผ ๋ชจ๋ ํ๋งคํด์ ์ป์ ์ ์๋ ์ต๋ ์์ต๊ตฌํ๊ธฐ => D[n]=n๊ฐ๋ฅผ ๋ชจ๋ ํ๋งคํด์ ์ป์ ์ ์๋ ์ต๋์์ต
๋ถ์ด๋นต ์
๊ฐ๊ฒฉ
๋จ์ ๋ถ์ด๋นต์ ์
์ต๋์์ต ๊ฐ๋ฅํ ๊ฒฝ์ฐ
1
P[1]
n-1
P[1]+D[n-1]
2
P[2]
n-2
P[2]+D[n-2]
...
...
...
...
n-1
P[n-1]
1
P[n-1]+D[1]
n
P[n]
0
P[n]+D[0]
=> D[n] = max(P[i]+D[n-i])(1<=i<=n)
#include <iostream>
using namespace std;
int d[10001];//๋ถ์ด๋นต n๊ฐ๋ฅผ ํ์์ ์ป์ ์ ์๋ ์ต๋์์ต
int p[10001];
int main(){
int n;//๋ถ์ด๋นต์ ์
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
d[i]=max(d[i],d[i-j]+p[j]);
}
}
cout<<d[n];
}
์ฌ์ด ๊ณ๋จ ์
์ธ์ ํ ์๋ฆฌ์ ์ฐจ์ด๊ฐ 1์ด ๋๋ ์๋ฅผ ๊ณ๋จ ์๋ผ๊ณ ํ๋ค. ex)45656 ๊ธธ์ด๊ฐ N์ธ ๊ณ๋จ ์์ ๊ฐ์๋ฅผ ๊ตฌํ์ฌ๋ผ.(0์ผ๋ก ์์ํ๋ ์๋ ์๋ค.)
=> D[N][L]=N์๋ฆฌ ๊ณ๋จ์, ๋ง์ง๋ง ์ L L -> L+1 or L-1 => D[N][L]=D[N-1][L-1]+D[N-1]+D[L+1]
#include <iostream>
using namespace std;
int d[101][9];
int main(){
int n,ans=0;
scanf("%d",&n);
for(int j=1;j<=9;j++){
d[1][j]=1;
}
for(int i=2;i<=n;i++){
for(int j=0;j<=9;j++){
d[i][j]=0;
if(j-1>=0)d[i][j]+=d[i-1][j-1];
if(j+1<=9)d[i][j]+=d[i-1][j+1];
}
}
for(int j=0;j<=9;j++){
ans+=d[n][j];
}
printf("%d",ans);
}
์ค๋ฅด๋ง ์
์ค๋ฅด๋ง ์๋ ์์ ์๋ฆฌ๊ฐ ์ค๋ฆ์ฐจ์์ ์ด๋ฃจ๋ ์๋ฅผ ๋งํ๋ค. ์ด ๋, ์ธ์ ํ ์๊ฐ ๊ฐ์๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์น๋ค. ์๋ฅผ ๋ค์ด, 2234์ 3678, 11119๋ ์ค๋ฅด๋ง ์์ด์ง๋ง, 2232, 3676, 91111์ ์ค๋ฅด๋ง ์๊ฐ ์๋๋ค. ์์ ๊ธธ์ด N์ด ์ฃผ์ด์ก์ ๋, ์ค๋ฅด๋ง ์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ 0์ผ๋ก ์์ํ ์ ์๋ค.
=> D[N][L]=N์๋ฆฌ ์ค๋ฅด๋ง์, ๋ง์ง๋ง์ L => D[N][L]=sum(D[N-1][k])(0<=k<=L)
#include <iostream>
using namespace std;
int d[1001][10];
int main(){
int n;
scanf("%d",&n);
for(int j=0;j<=9;j++){
d[1][j]=1;
}
for(int i=2;i<=n;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=j;k++)
d[i][j]+=d[i-1][k];
int ans=0;
for(int j=0;j<=9;j++){
ans+=d[n][j];
}
printf("%d",ans);
}
์ด์น์
0๊ณผ 1๋ก๋ง ์ด๋ฃจ์ด์ง ์๋ฅผ ์ด์ง์๋ผ ํ๋ค. ์ด๋ฌํ ์ด์ง์ ์ค ํน๋ณํ ์ฑ์ง์ ๊ฐ๋ ๊ฒ๋ค์ด ์๋๋ฐ, ์ด๋ค์ ์ด์น์(pinary number)๋ผ ํ๋ค. ์ด์น์๋ ๋ค์์ ์ฑ์ง์ ๋ง์กฑํ๋ค.
์ด์น์๋ 0์ผ๋ก ์์ํ์ง ์๋๋ค.
์ด์น์์์๋ 1์ด ๋ ๋ฒ ์ฐ์์ผ๋ก ๋ํ๋์ง ์๋๋ค. ์ฆ, 11์ ๋ถ๋ถ ๋ฌธ์์ด๋ก ๊ฐ์ง ์๋๋ค.
์๋ฅผ ๋ค๋ฉด 1, 10, 100, 101, 1000, 1001 ๋ฑ์ด ์ด์น์๊ฐ ๋๋ค. ํ์ง๋ง 0010101์ด๋ 101101์ ๊ฐ๊ฐ 1, 2๋ฒ ๊ท์น์ ์๋ฐฐ๋๋ฏ๋ก ์ด์น์๊ฐ ์๋๋ค.
=> D[n]=D[n-1]+D[n-2] (n์๋ฆฌ 2์น์ = n๋ฒ์งธ ์๋ฆฌ์ 0+n๋ฒ์งธ ์๋ฆฌ์ 1)
#include <iostream>
using namespace std;
int d[91];
int main(){
int n;
scanf("%d",&n);
d[1]=1;
d[2]=1;
for(int i=3;i<=n;i++){
d[i]=d[i-1]+d[i-2];
}
printf("%d",d[n]);
}
์คํฐ์ปค
์คํฐ์ปค 2n๊ฐ๊ฐ 2Xn๋ชจ์์ผ๋ก ๋ฐฐ์น๋์ด์๋ค. ์คํฐ์ปค ํ ์ฅ์ ๋ผ๋ฉด ๋ณ์ ๊ณต์ ํ๋ ์คํฐ์ปค๋ ๋ชจ๋ ์ฐข์ด์ ธ์ ์ฌ์ฉํ ์ ์๋ค. ์ ์์ ํฉ์ ์ต๋๋ก ๋ง๋๋ ๋ฌธ์ . ์ฆ, 2n๊ฐ์ ์คํฐ์ปค ์ค์์ ์ ์์ ํฉ์ด ์ต๋๊ฐ ๋๋ฉด์ ์๋ก ๋ณ์ ๊ณต์ ํ์ง ์๋ ์คํฐ์ปค ์งํฉ์ ๊ตฌํด์ผ ํ๋ค.
=> D[n][s]=2Xn ์คํฐ์ปค ์ํ s
s = 0์ ๋ฏ์ง ์์
D[n][0]=n-1์ด์์ ์คํฐ์ปค๋ฅผ ์ด๋ป๊ฒ ๋ฏ์๋์ง ์๊ด์ด ์๋ค. =>
max(D[n-1][0],D[n-1][1],D[n-1][2])
s = 1์ ์์ชฝ ์คํฐ์ปค ๋ฏ์
D[n][1]= n-1์ด์ ์์ชฝ ์คํฐ์ปค๋ ๋ฏ์ผ๋ฉด ์๋จ.
max(D[n-1][0],D[n-1][2])+A[n][0]
s = 2๋ ์๋์ชฝ ์คํฐ์ปค ๋ฏ์
D[n][1]= n-1์ด์ ์๋์ชฝ ์คํฐ์ปค๋ ๋ฏ์ผ๋ฉด ์๋จ.
max(D[n-1][0],D[n-1][1])+A[n][1]
=> max(D[n][0],D[n][1],D[n][2])
#include <iostream>
using namespace std;
int d[100000][3];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int array[n][2];
for(int i=0;i<2;i++){
for(int j=0;j<n;j++){
scanf("%d",&array[j][i]);
}
}
d[0][0]=0;
d[0][1]=array[0][0];
d[0][2]=array[0][1];
for(int i=1;i<n;i++){
d[i][0]=max(max(d[i-1][0], d[i-1][1]),d[i-1][2]);
d[i][1]=max(d[i-1][0],d[i-1][2])+array[i][0];
d[i][2]=max(d[i-1][0],d[i-1][1])+array[i][1];
}
printf("%d\n",max(max(d[n-1][0],d[n-1][1]),d[n-1][2]));
}
}
ํฌ๋์ฃผ์์
ํฌ๋์ฃผ ์์ ์ ํํ๋ฉด ๊ทธ ์์ ๋ค์ด์๋ ํฌ๋์ฃผ๋ ๋ชจ๋ ๋ง์ ์ผ ํ๊ณ , ๋ง์ ํ์๋ ์๋ ์์น์ ๋ค์ ๋์์ผ ํ๋ค.
์ฐ์์ผ๋ก ๋์ฌ ์๋ 3์์ ๋ชจ๋ ๋ง์ค ์๋ ์๋ค.
1๋ถํฐ n๊น์ง์ ๋ฒํธ๊ฐ ๋ถ์ด ์๋ n๊ฐ์ ํฌ๋์ฃผ ์์ด ์์๋๋ก ํ ์ด๋ธ ์์ ๋์ฌ ์๊ณ , ๊ฐ ํฌ๋์ฃผ ์์ ๋ค์ด์๋ ํฌ๋์ฃผ์ ์์ด ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๋ง์ ์์ ํฌ๋์ฃผ๋ฅผ ๋ง์ค ์ ์๋๋ก ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
D[i][j] = A[1]~A[n]๊น์ง ํฌ๋์ฃผ๋ฅผ ๋ง์ ง์ ๋ ๋ง์ค ์ ์๋ ํฌ๋์ฃผ์ ์ต๋ ์
0๋ฒ์ฐ์ : A[i]๋ฅผ ๋ง์์ง ์์
max(D[i-1][0],D[i-1][1],D[i-1][2])
1๋ฒ์ฐ์ : A[i-1]์ ๋ง์์ง ์์.
D[i-1][0]+A[i]
2๋ฒ์ฐ์ : A[i-1]๋ง์๊ณ , A[i-2]๋ง์์ง ์์
D[i-1][1]+A[i]
#include <iostream>
using namespace std;
int d[10001][3];
int main(){
int n;
scanf("%d",&n);
int g[n];
for(int i=1;i<=n;i++){
scanf("%d",&g[i]);
}
d[0][0]=d[0][1]=d[0][2]=0;
for(int i=1;i<=n;i++){
d[i][0]= max(max(d[i-1][0],d[i-1][1]),d[i-1][2]);
d[i][1]= d[i-1][0]+g[i];
d[i][2]= d[i-1][1]+g[i];
}
printf("%d",max(max(d[n][0],d[n][1]),d[n][2]));
}
D[i] = A[1]~A[n]๊น์ง ํฌ๋์ฃผ๋ฅผ ๋ง์ ง์ ๋ ๋ง์ค ์ ์๋ ํฌ๋์ฃผ์ ์ต๋ ์
0๋ฒ์ฐ์ : A[i]๋ฅผ ๋ง์์ง ์์
D[i-1]
1๋ฒ์ฐ์ : A[i-1]์ ๋ง์์ง ์์.
D[i-2]+A[i]
2๋ฒ์ฐ์ : A[i-1]๋ง์๊ณ , A[i-2]๋ง์์ง ์์
D[i-3]+A[i-1]+A[i]
=> D[i]=max(D[i-1], D[i-2]+A[i], D[i-3]+A[i-1]+A[i])
d[0]=0;
d[1]=g[1];
d[2]=g[1]+g[2];
for(int i=3;i<=n;i++){
d[i]= max(max(d[i-1],d[i-2]+g[i]),d[i-3]+g[i]+g[i-1]);
}
๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด
์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์) ์์ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด๊ณ , ๊ธธ์ด๋ 4์ด๋ค.
D[i]= A[1]~A[n]๊น์ง ์์ด์ด ์์ ๋, A[i]๋ฅผ ๋ง์ง๋ง์ผ๋ก ํ๋ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด(A[i]๋ฅผ ๋ฐ๋์ ํฌํจํด์ผํ๋ค.)
#include <iostream>
using namespace std;
int d[1001];
int main(){
int n; //์์ด์ ํฌ๊ธฐ
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
d[i]=1;
for(int j=0;j<i;j++){
if(a[i]>a[j]&&d[i]<d[j]+1)d[i]=d[j]+1;
}
}
int maxd=0;
for(int i=0;i<n;i++){
if(maxd<d[i])maxd=d[i];
}
printf("%d",maxd);
}
๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด
์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์) ์์ด A = {10, 30, 10, 20, 20, 10} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด์ A = {10, 30, 10, 20, 20, 10} ์ด๊ณ , ๊ธธ์ด๋ 3์ด๋ค.
D[i]= A[1]~A[n]๊น์ง ์์ด์ด ์์ ๋, A[i]๋ฅผ ๋ง์ง๋ง์ผ๋ก ํ๋ ๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด(A[i]๋ฅผ ๋ฐ๋์ ํฌํจํด์ผํ๋ค.)
#include <iostream>
using namespace std;
int d[1001];
int main(){
int n; //์์ด์ ํฌ๊ธฐ
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
d[i]=1;
for(int j=0;j<i;j++){
if(a[i]<a[j]&&d[i]<d[j]+1)d[i]=d[j]+1;
}
}
int maxd=0;
for(int i=0;i<n;i++){
if(maxd<d[i])maxd=d[i];
}
printf("%d",maxd);
}
๊ฐ์ฅ ๊ธด ๋ฐ์ดํ ๋ ๋ถ๋ถ ์์ด
์์ด S๊ฐ ์ด๋ค ์ Sk๋ฅผ ๊ธฐ์ค์ผ๋ก S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN์ ๋ง์กฑํ๋ค๋ฉด, ๊ทธ ์์ด์ ๋ฐ์ดํ ๋ ์์ด์ด๋ผ๊ณ ํ๋ค.
์) {10, 20, 30, 25, 20}๊ณผ {10, 20, 30, 40}, {50, 40, 25, 10} ์ ๋ฐ์ดํ ๋ ์์ด์ด์ง๋ง, {1, 2, 3, 2, 1, 2, 3, 2, 1}๊ณผ {10, 20, 30, 40, 20, 30} ์ ๋ฐ์ดํ ๋ ์์ด์ด ์๋๋ค.
๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด(D1)๊ณผ ๊ฐ์ฅ ๊ธด ๊ฐ์ํ๋ ๋ถ๋ถ ์์ด(D2)๋ฅผ ๊ตฌํ๋ค์ D1+D2-1์ ๊ตฌํ๋ฉด๋๋ค.
#include <stdio.h>
/*
์์ด S๊ฐ ์ด๋ค ์ Sk๋ฅผ ๊ธฐ์ค์ผ๋ก S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN์ ๋ง์กฑํ๋ค๋ฉด, ๊ทธ ์์ด์ ๋ฐ์ดํ ๋ ์์ด์ด๋ผ๊ณ ํ๋ค.
์๋ฅผ ๋ค์ด, {10, 20, 30, 25, 20}๊ณผ {10, 20, 30, 40}, {50, 40, 25, 10} ์ ๋ฐ์ดํ ๋ ์์ด์ด์ง๋ง, {1, 2, 3, 2, 1, 2, 3, 2, 1}๊ณผ {10, 20, 30, 40, 20, 30} ์ ๋ฐ์ดํ ๋ ์์ด์ด ์๋๋ค.
์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ทธ ์์ด์ ๋ถ๋ถ ์์ด ์ค ๋ฐ์ดํ ๋ ์์ด์ด๋ฉด์ ๊ฐ์ฅ ๊ธด ์์ด์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๊ณ , ๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 โค N โค 1,000, 1 โค Ai โค 1,000)
*/
int d[1001];
int d2[1001];
int main() {
int n;
scanf("%d",&n);
int a[n+1];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
d[i]=1;
for(int j=0;j<=i;j++){
if(a[i]>a[j]&&d[i]<d[j]+1){
d[i]=d[j]+1;
}
}
}
for (int i=n-1; i>=0; i--) {
d2[i] = 1;
for (int j=i+1; j<n; j++) {
if (a[i] > a[j] && d2[j]+1 > d2[i]) {
d2[i] = d2[j]+1;
}
}
}
int ans =0 ;
for(int i=0;i<n;i++){
if(ans<d[i]+d2[i]-1){
ans=d[i]+d2[i]-1;
}
}
printf("%d",ans);
return 0;
}
์ฐ์ํฉ
n๊ฐ์ ์ ์๋ก ์ด๋ฃจ์ด์ง ์์์ ์์ด์ด ์ฃผ์ด์ง๋ค. ์ฐ๋ฆฌ๋ ์ด ์ค ์ฐ์๋ ๋ช ๊ฐ์ ์ซ์๋ฅผ ์ ํํด์ ๊ตฌํ ์ ์๋ ํฉ ์ค ๊ฐ์ฅ ํฐ ํฉ์ ๊ตฌํ๋ ค๊ณ ํ๋ค. ๋จ, ์ซ์๋ ํ ๊ฐ ์ด์ ์ ํํด์ผ ํ๋ค.
์) 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 ์ด๋ผ๋ ์์ด์ด ์ฃผ์ด์ก๋ค๊ณ ํ์. ์ฌ๊ธฐ์ ์ ๋ต์ 12+21์ธ 33์ด ์ ๋ต์ด ๋๋ค.
D[i]=A[i]๋ก ๋๋๋ ์ต๋ ์ฐ์ํฉ
A[i-1]๋ก ๋๋๋ ์ฐ์ํฉ์ ํฌํจ D[i-1]+A[i]
์๋ก์ด ์ฐ์ํฉ ์์ A[i]
#include <iostream>
using namespace std;
int d[100001]; //A[i]๋ก ๋๋๋ ์ต๋ ์ฐ์ํฉ
int main(){
int n; //์ฐ์๋ ์ซ์์ ์
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
d[0]=a[0];
for(int i=1;i<n;i++){
d[i]=max(d[i-1]+a[i],a[i]);
}
int ans=d[0];
for(int i=1;i<n;i++){
if(ans<d[i])ans=d[i];
}
printf("%d",ans);
}
๊ณ๋จ ์ค๋ฅด๊ธฐ
๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ฒ์์ ๊ณ๋จ ์๋ ์์์ ๋ถํฐ ๊ณ๋จ ๊ผญ๋๊ธฐ์ ์์นํ ๋์ฐฉ์ ๊น์ง ๊ฐ๋ ๊ฒ์์ด๋ค. ๊ฐ๊ฐ์ ๊ณ๋จ์๋ ์ผ์ ํ ์ ์๊ฐ ์ฐ์ฌ ์๋๋ฐ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด ๊ทธ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๋ฅผ ์ป๊ฒ ๋๋ค.
๊ณ๋จ์ ํ ๋ฒ์ ํ ๊ณ๋จ์ฉ ๋๋ ๋ ๊ณ๋จ์ฉ ์ค๋ฅผ ์ ์๋ค. ์ฆ, ํ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด์ ์ด์ด์ ๋ค์ ๊ณ๋จ์ด๋, ๋ค์ ๋ค์ ๊ณ๋จ์ผ๋ก ์ค๋ฅผ ์ ์๋ค.
์ฐ์๋ ์ธ ๊ฐ์ ๊ณ๋จ์ ๋ชจ๋ ๋ฐ์์๋ ์๋๋ค. ๋จ, ์์์ ์ ๊ณ๋จ์ ํฌํจ๋์ง ์๋๋ค.
๋ง์ง๋ง ๋์ฐฉ ๊ณ๋จ์ ๋ฐ๋์ ๋ฐ์์ผ ํ๋ค.
๋ฐ๋ผ์ ์ฒซ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ณ ์ด์ด ๋ ๋ฒ์งธ ๊ณ๋จ์ด๋, ์ธ ๋ฒ์งธ ๊ณ๋จ์ผ๋ก ์ค๋ฅผ ์ ์๋ค. ํ์ง๋ง, ์ฒซ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ณ ์ด์ด ๋ค ๋ฒ์งธ ๊ณ๋จ์ผ๋ก ์ฌ๋ผ๊ฐ๊ฑฐ๋, ์ฒซ ๋ฒ์งธ, ๋ ๋ฒ์งธ, ์ธ๋ฒ์งธ ๊ณ๋จ์ ์ฐ์ํด์ ๋ชจ๋ ๋ฐ์ ์๋ ์๋ค.
D[i][j]=i๋ฒ์งธ ๊ณ๋จ์ ์ฌ๋์ ๋ ์ด ์ ์์ ์ต๋๊ฐ. (i๋ฒ์งธ ๊ณ๋จ์ j๊ฐ ์ฐ์ํด์ ์ค๋ฅธ ๊ณ๋จ)
D[i][0]=0๊ฐ์ฐ์(i๋ฒ์งธ ๊ณ๋จ์ ์ฌ๋ผ๊ฐ์ผ ํ๊ธฐ ๋๋ฌธ์ ๋ถ๊ฐ๋ฅํ ๊ฒฝ์ฐ)
D[i][1]=1๊ฐ์ฐ์(i-1์ ๋ฐ์ผ๋ฉด ์๋๋ค.)=max(D[i-2][1],D[i-2][2])+a[i]
D[i][2]=2๊ฐ์ฐ์(i๋ฒ์งธ ๊ณ๋จ์ ๋ฐ์์ผํ๊ณ , ๋ฐ๋์ 1๊ฐ ์ฐ์ํด์ ์ฌ๋ผ์จ ๊ณ๋จ์ด์ด์ผํ๋ค.)=D[i-1][1]+a[i]
#include <iostream>
using namespace std;
int d[301][3]; //A[i]๋ก ๋๋๋ ์ต๋ ์ ์
int main(){
int n; //๊ณ๋จ์
scanf("%d",&n);
int a[n];//๊ฐ ๊ณ๋จ ์ ์
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
d[0][1]=a[0];
d[1][1]=a[1];
d[1][2]=a[1]+a[0];
for(int i=2;i<n;i++){
d[i][1]=max(d[i-2][1],d[i-2][2])+a[i];
d[i][2]=d[i-1][1]+a[i];
}
printf("%d",max(d[n-1][1],d[n-1][2]));
}
์ด๋ ๊ฒฝ์ฐ์ ์๋ก ๋ฐ์ผ๋ก ๋นผ์ค๋ค๋ฉด 2์ฐจ์์์ 1์ฐจ์์ผ๋ก ์ฐจ์์ ์ค์ผ ์ ์๋ค.
D[i]=i๋ฒ์งธ ๊ณ๋จ์ ์ฌ๋ผ๊ฐ์ ๋, ์ต๋ ์ ์
1๊ฐ ์ฐ์ : i-1๋ฒ์งธ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด ์๋จ
i-2๋ ๋ฐ๋์ ๋ฐ์์ด์ผ ํจ
D[i-2]+A[i]
2๊ฐ ์ฐ์ : i-1๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ณ , i-2๋ ๋ฐ์ผ๋ฉด ์๋จ
i-3๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๋์ ๋ฐ์์ผ ํจ
D[i-3]+A[i-1]+A[i]
#include <iostream>
using namespace std;
int d[301]; //A[i]๋ก ๋๋๋ ์ต๋ ์ ์
int a[301];//๊ฐ ๊ณ๋จ ์ ์
int main(){
int n; //๊ณ๋จ์
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
d[1]=a[1];
d[2]=a[1]+a[2];
for(int i=3;i<=n;i++){
d[i]=max(d[i-2]+a[i],d[i-3]+a[i-1]+a[i]);
}
printf("%d",d[n]);
}
์ ๊ณฑ์์ ํฉ
์ด๋ค ์์ฐ์ N์ ๊ทธ๋ณด๋ค ์์ ์ ๊ณฑ์๋ค์ ํฉ์ผ๋ก ๋ํ๋ผ ์ ์๋ค. ์๋ฅผ ๋ค์ด 11=3^2+1^2+1^2(3๊ฐ ํญ)์ด๋ค. ์ด๋ฐ ํํ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ๋ ์ ์๋๋ฐ, 11์ ๊ฒฝ์ฐ 11=2^2+2^2+1^2+1^2+1^2(5๊ฐ ํญ)๋ ๊ฐ๋ฅํ๋ค. ์ด ๊ฒฝ์ฐ, ์ํ์ ์ํฌ๋ผํ ์ค๋ โ11์ 3๊ฐ ํญ์ ์ ๊ณฑ์ ํฉ์ผ๋ก ํํํ ์ ์๋ค.โ๋ผ๊ณ ๋งํ๋ค. ๋ํ 11์ ๊ทธ๋ณด๋ค ์ ์ ํญ์ ์ ๊ณฑ์ ํฉ์ผ๋ก ํํํ ์ ์์ผ๋ฏ๋ก, 11์ ๊ทธ ํฉ์ผ๋ก์จ ํํํ ์ ์๋ ์ ๊ณฑ์ ํญ์ ์ต์ ๊ฐ์๋ 3์ด๋ค.
D[i]=์์ฐ์ N์ ์ด๋ ๊ฒ ์ ๊ณฑ์๋ค์ ํฉ์ผ๋ก ํํํ ๋์ ๊ทธ ํญ์ ์ต์๊ฐ์
๋ง์ง๋งํญ์ด ์ค์ํ๋ค.
min(D[i-j^2]+1) (1<=i<=j^2)
#include <iostream>
using namespace std;
int d[100001]; //์ ๊ณฑํฉ์ผ๋ก ํํํ๋ ์ต์ํญ ๊ฐ์
int main(){
int n; //์์ฐ์
scanf("%d",&n);
for(int i=1;i<=n;i++){
d[i]=i; //1^2์ผ๋ก ํํํ ๊ฐ์(์ฆ, ์ต๋ํญ)
for(int j=1;j*j<=i;j++){
if(d[i]>d[i-j*j]+1)d[i]=d[i-j*j]+1;
}
}
printf("%d",d[n]);
}
ํ์ผ ์ฑ์ฐ๊ธฐ
3รN ํฌ๊ธฐ์ ๋ฒฝ์ 2ร1, 1ร2 ํฌ๊ธฐ์ ํ์ผ๋ก ์ฑ์ฐ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํด๋ณด์.
D[i]=3Xi๋ฅผ ์ฑ์ฐ๋ ๋ฐฉ๋ฒ์ ์
D[i]=3*D[i-2]+2*D[i-4]+2*D[i-6]+...
#include <iostream>
using namespace std;
int d[31]; //3*i๋ฅผ ํํํ ์ ์๋ ๊ฒฝ์ฐ์ ์
int main(){
int n;
scanf("%d",&n);
d[0]=1;
for (int i=2; i<=n; i+=2) {
d[i] = d[i-2]*3;
for (int j=i-4; j>=0; j-=2) {
d[i] += d[j]*2;
}
}
printf("%d",d[n]);
}
ํ๋๋ฐ ์์ด

๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ผ๊ฐํ์ด ๋์ ๋ชจ์์ผ๋ก ๋์ฌ์ ธ ์๋ค. ์ฒซ ์ผ๊ฐํ์ ์ ์ผ๊ฐํ์ผ๋ก ๋ณ์ ๊ธธ์ด๋ 1์ด๋ค. ๊ทธ ๋ค์์๋ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์ ์ผ๊ฐํ์ ๊ณ์ ์ถ๊ฐํ๋ค. ๋์ ์์ ๊ฐ์ฅ ๊ธด ๋ณ์ ๊ธธ์ด๋ฅผ k๋ผ ํ์ ๋, ๊ทธ ๋ณ์ ๊ธธ์ด๊ฐ k์ธ ์ ์ผ๊ฐํ์ ์ถ๊ฐํ๋ค.
ํ๋๋ฐ ์์ด P(N)์ ๋์ ์ ์๋ ์ ์ผ๊ฐํ์ ๋ณ์ ๊ธธ์ด์ด๋ค. P(1)๋ถํฐ P(10)๊น์ง ์ฒซ 10๊ฐ ์ซ์๋ 1, 1, 1, 2, 2, 3, 4, 5, 7, 9์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, P(N)์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
D[i]=P(i)ํ๋๋ฐ ์์ด
D[i-2]+D[i-3]
D[i-5]+D[i-1]
#include <iostream>
using namespace std;
int d[101]; //ํ๋๋ฐ์์ด
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
d[0]=0;
d[1]=d[2]=1;
for (int i=3; i<=n; i++) {
d[i] = d[i-2]+d[i-3];
}
printf("%d\n",d[n]);
}
}
ํฉ๋ถํด
0๋ถํฐ N๊น์ง์ ์ ์ K๊ฐ๋ฅผ ๋ํด์ ๊ทธ ํฉ์ด N์ด ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ง์ ์ ์์๊ฐ ๋ฐ๋ ๊ฒฝ์ฐ๋ ๋ค๋ฅธ ๊ฒฝ์ฐ๋ก ์ผ๋ค(1+2์ 2+1์ ์๋ก ๋ค๋ฅธ ๊ฒฝ์ฐ). ๋ํ ํ ๊ฐ์ ์๋ฅผ ์ฌ๋ฌ ๋ฒ ์ธ ์๋ ์๋ค.
D[K][N]=์ ์ 0๋ถํฐ N๊น์ง์ ์ ์ K๊ฐ๋ฅผ ๋ํด์ N์ด ๋ง๋ค์ด์ง๋ ๊ฒฝ์ฐ์ ์
+=D[K-1][N-L] (0<=L<=N)
#include <iostream>
using namespace std;
long long int d[201][201]; //ํฉ๋ถํด
int main(){
int n,k;
scanf("%d %d",&k,&n);
d[0][0]=1LL;
for(int i=1;i<=k;i++){
for(int j=0;j<=n;j++){
for(int l=0;l<=j;l++){
d[i][j]+=d[i-1][j-l];
d[i][j]%=1000000000;
}
}
}
printf("%lld",d[k][n]);
}
์ํธ ์ฝ๋
์๊ทผ: ๊ทธ๋ฅ ๊ฐ๋จํ ์ํธํ ํ์. A๋ฅผ 1์ด๋ผ๊ณ ํ๊ณ , B๋ 2๋ก, ๊ทธ๋ฆฌ๊ณ Z๋ 26์ผ๋ก ํ๋๊ฑฐ์ผ. ์ ์: ๊ทธ๋ผ ์๋ผ. ๋ง์ฝ, "BEAN"์ ์ํธํํ๋ฉด 25114๊ฐ ๋์ค๋๋ฐ, ์ด๊ฑธ ๋ค์ ๊ธ์๋ก ๋ฐ๊พธ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ๊ฐ์ง๊ฐ ์์ด. ์๊ทผ: ๊ทธ๋ ๋ค. 25114๋ฅผ ๋ค์ ์์ด๋ก ๋ฐ๊พธ๋ฉด, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" ์ด 6๊ฐ์ง๊ฐ ๋์ค๋๋ฐ, BEAN์ด ๋ง๋ ๋จ์ด๋ผ๋๊ฑด ์ฝ๊ฒ ์์ ์์์? ์ ์: ์๊ฐ ์ ์ ํ์ง ์์๋ค ใ ใ ๋ง์ฝ ๋ด๊ฐ 500์๋ฆฌ ๊ธ์๋ฅผ ์ํธํ ํ๋ค๊ณ ํด๋ด. ๊ทธ ๋๋ ๋์ฌ ์ ์๋ ํด์์ด ์ ๋ง ๋ง์๋ฐ, ๊ทธ๊ฑธ ์ธ์ ๋คํด๋ด? ์๊ทผ: ์ผ๋ง๋ ๋ง์๋ฐ? ์ ์: ๊ตฌํด๋ณด์! ์ด๋ค ์ํธ๊ฐ ์ฃผ์ด์ก์ ๋, ๊ทธ ์ํธ์ ํด์์ด ๋ช ๊ฐ์ง๊ฐ ๋์ฌ ์ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
D[i]=i๋ฒ์งธ ๋ฌธ์๊น์ง ํด์ํ์ ๋, ๋์ฌ ์ ์๋ ํด์์ ๊ฐ์ง ์
1์๋ฆฌ ์ํธ(0์ ์ธ)
2์๋ฆฌ ์ํธ(10~26)
Last updated
Was this helpful?