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

www.acmicpc.net/problem/20500

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

문제 제목이 이게 무슨 개소리야;; 왠지 좆같은데.. 한남 냄새가 나..

 

아이디어:

1과 5로만 구성된 N자리 양의 정수 중, 15의 배수가 몇 개인지

 

15의 배수: 일의 자리는 0 or 5여야 하므로 일의 자리는 무조건 5, 각 자리의 합이 3의 배수여야 함.

5가 사용된 갯수 i에 따라 (1~N) 각 자릿수의 합을 구할 수 있음. -> 3의 배수인지 확인, 조합 이용(n-1Ci-1)

import sys
n = int(sys.stdin.readline())
ans = 0

#조합 구하기
N=n-1
dp = [0]*(N//2+1)
dp[0]=1 #nC0=1

for i in range(1,N//2+1):
    top=1
    bottom=1
    for k in range(N,N-i,-1):
        top*=k
    for k in range(1,i+1):
        bottom*=k
    dp[i]=top//bottom

for i in range(1,n+1):
    total = i*5 + (n-i)*1
    if ((total%3)==0):
        i = min(i-1,N-i+1)
        ans+=dp[i]
print(ans%1000000007)

n-1Ci-1인데 n으로 설계해서 삽질했음..

 

DP로 푸는 방법:

N자리까지 만들었고 뒤에 숫자 하나를 더 붙여서 n+1자리를 만든다고 생각..?

n자리까지 만들었을때 3으로 나눈 나머지와 뒤에 0을 하나 더 붙인 수의 3으로 나눈 나머지를 비교하면 어떨까요??

모르겠다....