[백준/수학] 3360번 깡총깡총

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

3360번: 깡총깡총

 

 

토끼가 3,2,1 미터씩 N 미터를 지난다.

이 때 길이가 증가하지 않는 순서로 지나가는 방법을 구하는 문제이다.

 

처음에는 재귀함수로 하려고 했는데 메모리가 초과되었다.

 

재귀함수보다 직접 계산하는 방법은 3을 맨 왼쪽으로 고정시키는 것이다.

그리고 2를 나눠줘서 2가 들어있는 갯수를 구해준다.

마지막에 +1 을 하는 이유는 1만으로 이뤄진 식을 고려하는 것이다.

이거 안해줘서...(っ °Д °;)っ

import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())

num = 0
def count(x,last):
    global num
   
    if x == 0:
        num += 1
        return 
    elif x<0:
        return
    else:
        if last == 3:
            count(x-3,3)
            count(x-2,2)
            count(x-1,1)
        elif last == 2:
            count(x-2,2)
            count(x-1,1)
        elif last == 1:
            count(x-1,1)

count(N,3)
print(num)

 

Python 으로 제출했더니 시간초과가 떠서, Pypy로 했다.

import sys

N = int(sys.stdin.readline())

#왼쪽을 고정시키기
num = 0

#3을 고정하면, 나머지는 1,2로 이뤄짐
#+1 은 1만 있는 경우
for i in range(N):
    if N >= 3*i:
        #2로 나눈 이유는 2가 맨 앞에 있을 수 있는 갯수
        num += (N-3*i)//2 + 1
        
print(num% 1000000)