백준 20500번 - Ezreal 여눈부터 가네 ㅈㅈ

https://www.acmicpc.net/problem/20500

20500번: Ezreal 여눈부터 가네 ㅈㅈ

 

문제 설명이 아주 깔끔해서 맘에 드는 문제다.

1과 5로만 구성된 n자리의 수가 15의 배수가 되는 경우의 수를 구해야 한다.

 

15는 3*5이므로 15의 배수는 5,0으로 끝나면서 자릿수의 합이 3의 배수여야한다.

즉 이 문제의 경우에는 1의 자릿수가 5가 되면서 총 자릿수들의 합이 3의 배수가 되면 된다.

 

자릿수가 3의 배수가 되는 경우에 한해 5151515, 1111115 같은 경우의 수를 계산해줘야 한다.

1의 자릿수는 5 고정이므로 앞의 n-1개의 자리에 5가 어디어디에 들어갈지 고려해줘야 한다.

 

nCr 조합의 nCr=n-1Cr + n-1Cr-1 의 공식을 활용해서 동적 계획법으로 계산해주면 해결할 수 있다.

 

#include <iostream>
#define MOD 1000000007

using namespace std;

int n;
int DP[2000][2000];

int ncr(int n, int r){
    if(DP[n][r]!=0)
        return DP[n][r];
    if(r==0){
        DP[n][r]=1;
        return 1;
    }
    if(r==1){
        DP[n][r]=n;
        return n;
    }
    if(n==r)
        return 1;
    DP[n][r]=(ncr(n-1,r-1)+ncr(n-1,r))%MOD;
    return DP[n][r];
}

int main(){
    int answer=0;
    cin>>n;
    for(int a=1; a<=n; a++){
        int b=n-a;
        if((a*5+b)%3==0){
            answer+=ncr(n-1,a-1);
            answer%=MOD;
        }
    }
    cout<<answer;
}