Dynamic Programming

큰 문제λ₯Ό μž‘μ€ 문제둜 λ‚˜λˆ μ„œ ν‘ΈλŠ” μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€.

  1. Overlapping Subproblem (κ²ΉμΉ˜λŠ” λΆ€λΆ„λ¬Έμ œ)

  2. Optimal Substructure(문제의 정닡을 μž‘μ€ λΆ€λΆ„μ—μ„œ μ•Œ 수 μžˆμ„ λ•Œ) : μž‘μ€ λ¬Έμ œμ—μ„œ κ΅¬ν•œ 정닡은 그것을 ν¬ν•¨ν•˜λŠ” 큰 λ¬Έμ œμ—μ„œλ„ λ™μΌν•˜λ‹€.

이 두가지 속성을 λ§Œμ‘±ν•΄μ•Ό λ‹€μ΄λ‚˜λ―Ή ν”„λ‘œκ·Έλž˜λ°μœΌλ‘œ 문제λ₯Ό ν’€ 수 μžˆλ‹€.

Overlapping Subproblem

  • 문제 : N번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • μž‘μ€λ¬Έμ œ : N-1번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제, N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • 문제 : N-1번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • μž‘μ€λ¬Έμ œ : N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제, N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • 문제 : N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

  • μž‘μ€λ¬Έμ œ : N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제, N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

μž‘μ€ λ¬Έμ œκ°€ κ²Ήμ³μ•Όν•œλ‹€. 큰 λ¬Έμ œμ™€ μž‘μ€ λ¬Έμ œλŠ” μƒλŒ€μ μ΄λ‹€.

  1. 큰 λ¬Έμ œμ™€ μž‘μ€ 문제λ₯Ό 같은 λ°©λ²•μœΌλ‘œ ν’€ 수 μžˆλ‹€.

  2. 문제λ₯Ό μž‘μ€ 문제둜 μͺΌκ°€ 수 μžˆλ‹€.

Optimal Substructure

문제의 정닡을 μž‘μ€ 문제의 μ •λ‹΅μ—μ„œ ꡬ할 수 μžˆλ‹€.

N-1번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제 = N-2번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제 + N-3번째 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό κ΅¬ν•˜λŠ” 문제

λ‹€μ΄λ‚˜λ―Ή ν”„λ‘œκ·Έλž˜λ°

  • 각 λ¬Έμ œλŠ” ν•œλ²ˆλ§Œ ν’€μ–΄μ•Ό ν•œλ‹€.

  • 같은 λ¬Έμ œλŠ” ꡬ할 λ•Œλ§ˆλ‹€ 정닡이 κ°™λ‹€.(Optimal Substructure)

  • 정닡을 κ΅¬ν–ˆμœΌλ©΄, 정닡을 μ–΄λ”˜κ°€μ— λ©”λͺ¨ν•΄λ†“λŠ”λ‹€.(λ°°μ—΄)=>Memoization

Top-down

  1. 문제λ₯Ό μž‘μ€ 문제둜 λ‚˜λˆˆλ‹€.

  2. μž‘μ€ 문제λ₯Ό ν‘Όλ‹€.

  3. μž‘μ€ 문제λ₯Ό ν’€μ—ˆμœΌλ‹ˆ, 이제 문제λ₯Ό ν‘Όλ‹€.

μž¬κ·€ν˜ΈμΆœμ„ μ΄μš©ν•΄μ„œ 문제λ₯Ό μ‰½κ²Œ ν’€ 수 μžˆλ‹€. μ‹œκ°„λ³΅μž‘λ„λŠ” μ±„μ›Œμ•Όν•˜λŠ” 칸의 수 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

  1. 문제λ₯Ό 크기가 μž‘μ€ λ¬Έμ œλΆ€ν„° μ°¨λ‘€λŒ€λ‘œ ν‘Όλ‹€.

  2. 문제의 크기λ₯Ό μ‘°κΈˆμ”© 크게 λ§Œλ“€λ©΄μ„œ 문제λ₯Ό ν‘Όλ‹€.

  3. μž‘μ€ 문제λ₯Ό ν’€λ©΄μ„œ μ™”κΈ° λ•Œλ¬Έμ—, 큰 λ¬Έμ œλŠ” 항상 ν’€ 수 μžˆλ‹€.

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]));
    }
}

ν¬λ„μ£Όμ‹œμ‹

  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);
}

계단 였λ₯΄κΈ°

계단 였λ₯΄κΈ° κ²Œμž„μ€ 계단 μ•„λž˜ μ‹œμž‘μ λΆ€ν„° 계단 κΌ­λŒ€κΈ°μ— μœ„μΉ˜ν•œ λ„μ°©μ κΉŒμ§€ κ°€λŠ” κ²Œμž„μ΄λ‹€. 각각의 κ³„λ‹¨μ—λŠ” μΌμ •ν•œ μ μˆ˜κ°€ μ“°μ—¬ μžˆλŠ”λ° 계단을 밟으면 κ·Έ 계단에 μ“°μ—¬ μžˆλŠ” 점수λ₯Ό μ–»κ²Œ λœλ‹€.

  1. 계단은 ν•œ λ²ˆμ— ν•œ 계단씩 λ˜λŠ” 두 계단씩 였λ₯Ό 수 μžˆλ‹€. 즉, ν•œ 계단을 λ°ŸμœΌλ©΄μ„œ μ΄μ–΄μ„œ λ‹€μŒ κ³„λ‹¨μ΄λ‚˜, λ‹€μŒ λ‹€μŒ κ³„λ‹¨μœΌλ‘œ 였λ₯Ό 수 μžˆλ‹€.

  2. μ—°μ†λœ μ„Έ 개의 계단을 λͺ¨λ‘ λ°Ÿμ•„μ„œλŠ” μ•ˆλœλ‹€. 단, μ‹œμž‘μ μ€ 계단에 ν¬ν•¨λ˜μ§€ μ•ŠλŠ”λ‹€.

  3. λ§ˆμ§€λ§‰ 도착 계단은 λ°˜λ“œμ‹œ λ°Ÿμ•„μ•Ό ν•œλ‹€.

    λ”°λΌμ„œ 첫 번째 계단을 밟고 이어 두 번째 κ³„λ‹¨μ΄λ‚˜, μ„Έ 번째 κ³„λ‹¨μœΌλ‘œ 였λ₯Ό 수 μžˆλ‹€. ν•˜μ§€λ§Œ, 첫 번째 계단을 밟고 이어 λ„€ 번째 κ³„λ‹¨μœΌλ‘œ μ˜¬λΌκ°€κ±°λ‚˜, 첫 번째, 두 번째, μ„Έλ²ˆμ§Έ 계단을 μ—°μ†ν•΄μ„œ λͺ¨λ‘ λ°Ÿμ„ μˆ˜λŠ” μ—†λ‹€.

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?