백준 10844번 쉬운 계단수

문제 이해가 잘 안됐는데 테스트케이스를 보니까 이해가 됐다

 

1부터 최대 자릿수까지 몇개의 계단수가 있는지 알아내면 된다

 

1의 경우는 1부터 9까지의 수가 있으니 9개

2의 경우는 

이런 느낌으로 가서

2부터 9까지 2개씩 있고 1은 한개 있으니 17이다

 

그럼 3은?

이런식으로 올라갔다 내려갔다를 다시 고려해야한다(내려갔다 올라갔다도 마찬가지)

 

조금 작은 문제로 쪼개 보자면

1로 시작하는 경우

2로 시작하는 경우 이런식으로 시작하는 숫자로 쪼갠뒤에

 

그 뒤 숫자들도 마찬가지로 나눠줘서 풀면 될듯하다

그리고 각 숫자들에 대해서는 저장을 해주기만 하면 될거 같다

 

오늘도 마찬가지로 탑다운이 아닌 바텀업으로 작성하는 연습을 해보겠다 나는 탑다운이 더 쉽고 바텀업이 더 어려우니까 일단 힘들더라도 바텀업으로 작성하는 연습을 하도록 하자

 

 

코드를 작성하려하니 고려해야할 사항이 추가로 있었다

선택된 숫자로 몇자리수를 만드느냐도 고려해야한다는 것이다

 

예를 들어 n=3일때 3으로 2자리를 만드는 경우는 2개이고 3으로 3자리수를 만드는 경우의 수는 3개이다

 

이런식으로 채우면 될거같다

1로 1자리수를 만들 수 있는 경우의 수

2로 1자리수를 만들 수 있느 경우의 수

3으로..

...

9로 만들 수 있는 경우의 수까지

 

저 자리수를 n까지 늘리면 될것같다

2자리수부터는 선택된 숫자에 1을 더하거나 뺀값을 또 골라서 자리수-1을 한뒤에 경우의 수를 계산하면된다

 

배열은 2차원이 필수인듯 하다

 

코드를 작성하다 안것인데 9도 사실 다음 숫자가 없으니까 추가 고려해야한다 그래서 n=2일때를 좀더 생각해보니

1이 두개이고 9가 한개라는 사실을 깨달았다

0으로 시작하면 안되는거지 0이 들어가면 안되는게 아닌것이었다

 

그래서 0도 되게하고 최종 개수 세기에서 0으로 시작하는 개수를 빼기로 했다

import sys

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

number=[[0]*10 for _ in range(n+1)]

for i in range(10):
    number[1][i]=1

for i in range(2,n+1):
    for j in range(1,10):
        if j==1:
            number[i][0]=number[i-1][1]
        if j+1<10:
            number[i][j]=(number[i-1][j-1]+number[i-1][j+1])%1000000000
        else:
            number[i][j]=(number[i-1][j-1]%1000000000)
        
result=0
for i in range(1,10):
    result=(result+number[n][i])%1000000000
print(result)

 

최종 코드다

 

처음에 이문제를 봤을때는 막막했는데 막상 해보니 2시간도 안걸렸다

dp도 하다보니 느는게 느껴져서 연습하는 보람이 있다