1, 2, 3 더하기 7

내일 시험이 있어서 간단한 문제로 한개 가져왔다. 실수 때문에 시간이 조금 오래걸렸다.

문제 분석

Crepe

위의 그림을 보면 바로 이해될 것이다. 예를 들어서 ‘5 3’은 3개의 숫자로 5를 만들 수 있는 가짓수이다. 따라서, 아래의 경우를 모두 더한 수와 같다고 할 수 있다.

  • 2개의 숫자로 4를 만들 수 있는 경우의 수 [ + ‘1’ ]
  • 2개의 숫자로 3를 만들 수 있는 경우의 수 [ + ‘2’ ]
  • 2개의 숫자로 2를 만들 수 있는 경우의 수 [ + ‘3’ ]

이렇게 dp는 빠르게 찾았는데, 입력을 받을 때, 숫자 두개를 dictionary에 저장하겠다는 판단을 하면서 시간을 많이 잡아먹게 되었다.

dictionary를 사용하면,

3
4 3
2 1
4 2

이렇게 들어오는 경우 순서대로 출력할 수 없게되는 문제가 있었다. {4:[3,2],2:[1]} 이런식으로 순서가 뒤죽박죽 되기 때문이다. 주의하자!


CODE

import sys
read=sys.stdin.readline

n=int(read())
num=[]
m=0
for _ in range(n):
    a,b=map(int,read().split())
    num.append([a,b])
    m=max(a,m)


dp=list(list(0 for _ in range(m+1)) for _ in range(m+1))
dp[1][1]=1
if m>1:
    dp[2][1]=1
    dp[2][2]=1
if m>2:
    dp[3][1]=1
    dp[3][2]=2
    dp[3][3]=1
#check=1
for i in range(4,m+1):
    for j in range(1,i+1):
        dp[i][j]=(dp[i-1][j-1]+dp[i-2][j-1]+dp[i-3][j-1])%1_000_000_009
        #if dp[i][j]==0: check+=1

for a,b in num:
    print(dp[a][b])


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]