백준 10844 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자

쉬운 계단 수?

 

어렵다.

 

n이 1, 2 일 때 9, 17 이길래 단순 dp문제인 줄 알았다.

 

그러다가 풀수록 뭔가 이상함을 느꼈다.

 

끝자리가 0과 9일 때 변수가 생겨 해당 부분을 따로 계산해야 했다.

 

그냥 내 접근 방식 자체가 틀렸다.

 

처음엔 만든 코드다.

a = int(input())

dp = [9,17] * (50+1)

for j in range(2,a):

    if j % 2 == 0 :

        dp[j] = dp[j-1]*2

    else :

        dp[j] = (dp[j-1]-1)*2 + 1

       

print(dp[a-1]%1000000000)

너무 안일하게 생각했던 탓이다.

 

아직까지 이 문제를 완벽하게 이해하지 못했다.

 

정답 코드 먼저 올린다.

a = int(input())

dp = [[0 for i in range(10)] for j in range(a+1)]

for i in range(1, 10):

    dp[1][i] = 1

   

for i in range(2, a + 1):

    for j in range(10):

        if j == 0:

            dp[i][j] = dp[i - 1][1]

        elif j == 9:

            dp[i][j] = dp[i - 1][8]

        else:

            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

print(sum(dp[a])%1000000000)

출처 : https://pacific-ocean.tistory.com/151

[백준] 10844번(python 파이썬)

 

끝자리가 0과 9일 때, 다음 단계에서 파생되는 수가 당연히 1일 거라 생각했는데, 아니다.

 

추후에 이해가 되면 더 포스팅하겠다.

 

맞춤법 검사를 하고, 태그를 작성한 후 이대로 작성하기에 너무 찝찝한 느낌이 들었다.

그래서 배열로 출력해본 뒤 마지막으로 봤다.

 

바로 이해했다.

 

사진으로 첨부한다.

10은 그냥 배열을 출력하기 위해 막 넣은 숫자이다.

 

배열의 각 위치(0~9)에 저장된 값은 각 위치 인덱스로 끝나는 수의 개수이다.

 

해당 관점에서 배열을 바라보면 이해가 된다.

 

이해했다...

 

a = int(input())

dp = [[0 for i in range(10)] for j in range(a+1)]

for i in range(1, 10):

    dp[1][i] = 1

   

for i in range(2,a+1):

    for j in range(10):

        if j == 0:

            dp[i][j] = dp[i-1][j+1]

        elif j == 9:

            dp[i][j] = dp[i-1][j-1]

        else:

            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

           

print(sum(dp[a])%1000000000)

배운 점

1. dp 너무 어려워.. 풀고나면 쉬워..