20500번: Ezreal 여눈부터 가네 ㅈㅈ
문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.
www.acmicpc.net
문제 제목이 이게 무슨 개소리야;; 왠지 좆같은데.. 한남 냄새가 나..
아이디어:
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으로 나눈 나머지를 비교하면 어떨까요??
모르겠다....
'알고리즘💻 > DP' 카테고리의 다른 글
BOJ 12865번: 평범한 배낭 (0) | 2021.01.24 |
---|---|
BOJ 14494번: 다이나믹이 뭐예요? (0) | 2021.01.24 |
BOJ 1463번: 1로 만들기 (0) | 2021.01.24 |
BOJ 1757번: 달려달려 (0) | 2021.01.24 |
BOJ 15988번: 1, 2, 3 더하기 3 (0) | 2021.01.24 |