백준 16194번 1,2,3 더하기 5

1,2,3 더하기랑 비슷한데 많이 다르다

연속 2번이 불가능하다 중복이 불가능한게 아니다

 

전에 풀었던 카드구매하기랑 유사한점이 보인다

1,2,3벽돌을 이용해서 n층의 탑을 쌓아야한다

이렇게 접근 할 수 있을것같다

 

다만 이렇게 간단하게 끝나지 않고 "연속해서 등장할 수 없다"라는 점을 생각해야한다

그래서 이 접근은 잘못됐을거라고 생각했고

이런 그래프라고 생각해보기로 했다

 

1에서 출발하는거

2에서 출발하는거

3에서 출발하는거

이 세개에서 합이 n이 되는 애들을 개수를 구하면 될거같다

 

import sys

t=int(sys.stdin.readline().rstrip())

for _ in range(t):
    n=int(sys.stdin.readline().rstrip())

    v=[0]*(n+1)

    def dp(n,state=0):
        if n<0:
            return 0
        elif n==0:
            return 1
        if state==0:
            v[n] = dp(n-1,1)+dp(n-2,2)+dp(n-3,3)
        else:
            v[n] = dp(n-1,1)+dp(n-2,2)+dp(n-3,3)-dp(n-state,state)
        return v[n]
    
    print(dp(n))

그래서 코드를 이렇게 dfs느낌으로 작성했다(아직 완성된 코드가 아니다 답은 나오는데 시간초과 날거임)넣어도 상당히 오래걸린다 이렇게 작성하면 시간복잡도는 O(2^n)이다

n은 최대 10^5이므로 무조건 시간초과가 걸릴것이다

(추가로 재귀횟수 제한도 걸릴거고)

 

 

 

중복을 제거하기 위해 코드를 수정하자

def dp(n,state=0):
        if n<0:
            return 0
        elif n==0:
            return 1
        if v[n]!=0:
            return v[n]-dp(n-state,state)
        if state==0:
            v[n] = dp(n-1,1)+dp(n-2,2)+dp(n-3,3)
        else:
            v[n] = dp(n-1,1)+dp(n-2,2)+dp(n-3,3)-dp(n-state,state)
        return v[n]

수정을 좀 해봤는데 4는 맞게 나오는데 7이 틀리게나온다

예를들어 3을 이미 구한경우 저장된 3의 값-dp(3,노드번호)이런 의도로 작성했는데 정상적으로 동작하지 않았나보다

 

조금더 수정해줬다

import sys

t=int(sys.stdin.readline().rstrip())

for _ in range(t):
    n=int(sys.stdin.readline().rstrip())

    v = [[0] * 4 for _ in range(n+1)]

    def dp(n,state=0):
        if n<0:
            return 0
        elif n==0:
            return 1
        
        if v[n][state]!=0:
            return v[n][state]
        
        if state==0:
            v[n] = (dp(n-1,1)+dp(n-2,2)+dp(n-3,3))%1000000009
            return v[n]
        else:
            v[n][state] = dp(n-1,1)+dp(n-2,2)+dp(n-3,3)-dp(n-state,state)%1000000009
            return v[n][state]
        
    
    print(dp(n))

 

v를 2차원으로 만들어서 해당 숫자의 이전 state가 몇인가에 따라 몇 개인지를 저장하게끔 했다

물론 이번에는 재귀 제한에 걸리지만 조금만 더 수정하면 될거같다

(리스트 컴프리헨션 부분은 처음에 v=[[0]*(3+1)]*(n+1) 로 했다가 이렇게 만들면 얇은복사만 된다는걸 몰라서 삽질 좀 했다)

 

아무튼 답은 멀쩡히 나오지만 문제는 재귀제한에 걸린다는거다

100을 넣어도 즉시 답이 나오므로 접근 방법 자체는 이게 맞는 듯 하다.

입력제한이 10^6이므로 재귀제한을 피하려면 재귀를 n/100까지만 들어가야하는데 쉽지않을 듯 하다

(10^5인줄 알고 재귀제한 풀고 제출했다가 재귀오류 걸렸다...)

 

 

그렇다면 이걸 그대로 바텀 업으로 구현한다면 되지않을까?

 

import sys

t=int(sys.stdin.readline().rstrip())

for _ in range(t):
    n=int(sys.stdin.readline().rstrip())

    v = [[0] * 4 for _ in range(n+1)]

    v[1][1]=1
    v[2][2]=1
    v[3][1]=1
    v[3][2]=1
    v[3][3]=1

    for i in range(1,n+1):
        for j in range(1,3+1):
            if i>3:
                v[i][j]+=((v[i-j][1]+v[i-j][2]+v[i-j][3]-v[i-j][j])%1000000009)
        v[i][0]=(v[i][1]+v[i][2]+v[i][3])%1000000009
    
    print(v[n][0])

 

분명 탑다운을 바텀업으로 바꾸는건데 4시간가까이 걸렸다...

초기값 부분에서 좀 헤맸다

 

이 코드로 제출을 했더니

??? 이게 왜 시간초과야? O(n)이잖아?

 

하고 다시 코드를 잘 살펴보니 입력받을때마다 n까지 초기화 하는 방식이라서 그런것 같다 그냥 10^5까지 값을 구해놓고 바로 출력하는걸로 다시 작성하자

import sys

t=int(sys.stdin.readline().rstrip())

n=100000
v = [[0] * 4 for _ in range(n+1)]
v[1][1]=1
v[2][2]=1
v[3][1]=1
v[3][2]=1
v[3][3]=1

for i in range(1,n+1):
    for j in range(1,3+1):
        if i>3:
            v[i][j]+=((v[i-j][1]+v[i-j][2]+v[i-j][3]-v[i-j][j])%1000000009)
    v[i][0]=(v[i][1]+v[i][2]+v[i][3])%1000000009

for _ in range(t):
    in_n=int(sys.stdin.readline().rstrip())
    
    
    print(v[in_n][0])

 

총 9시간 정도 걸린것같다

 

 

그런데 오늘도 마찬가지로 다른사람들보다 2배가량 느리다 도대체 왤까

이번주까지도 이유를 자력으로 못알아내면 그냥 다른사람 풀이를 봐야겠다