문제

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 $N$자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.

참가자 여러분도 궁금하지요?

안 궁금함? 15ㄱ

입력

 $N$이 주어진다.

출력

문제의 답을 $1000000007$로 나눈 나머지를 출력한다.

제한

 1<N<1516

풀이

dfs를 이용해서 한자리수부터 10자리수 정도까지 추가해가면서 그 값이 15로 나눠지는 갯수를 세어보았다 . 1과 5가 둘다 사용되어야 한다고 생각했는데 그건 또 아니었다.
하여튼 갯수를 세어서 규칙을 찾아보았는데 홀수일 경우는 전의 것 2배에 -1 짝수일 경우는 전의두배에 +1 라는 규칙을 찾을 수 있었다.

N자리에 15로 나눠지는게 몇개 있는지 확인하는 코드

result =[]
count=0
def dfs(strnum):
   global count
   if len(strnum) == N:
       return
   for one_five in ['1','5']:
       newnum = strnum + one_five
       if int(newnum)%15 ==0 and len(newnum)==N:
           count+=1
           result.append(newnum)
           # print(newnum)
       dfs(newnum)

dfs("")

```python
import sys
sys.stdin = open('input.txt')

# 15의 배수라는 것은 다 합쳐서 3의 배수 + 맨뒷자리가 5

N = int(input())
dp = [0]*(1516)
# 0 1 2 3 4 5  6  7  8  9   10  11  12   13   14
# 0,0,1,1,3,5, 11,21,43,85,171,341,683,1365 ,2731
# 0
dp[1]= 0
dp[2]= 1
dp[3]= 1

for i in range(4,1516):
   if i%2==0:
       dp[i]= (dp[i-1]*2 +1)%1000000007
   else:
       dp[i]= (dp[i-1]*2 -1)%1000000007

print(dp[N])