백준 - 10844번

import sys

n = int(sys.stdin.readline())
cnt = 0


for k in range(10**(n-1),10**n):
    k = list(str(k))
    for i in range(len(k)):
        if len(k) > 1:
            try:
                if abs(int(k[i]) - int(k[i + 1])) == 1:
                    cnt = cnt + 1
            except IndexError:
                pass
        elif len(k) == 1:
            cnt = 9


print(cnt%1000000000)

답은 나오지만 시간 효율이 매우 떨어지는 알고리즘이다.

숫자를 하나하나 받아서 문자열로 변환 후 비교하는 알고리즘이니 그럴 법도 하다.

백준에서 시간초과가 떠버렸다. 다른 알고리즘을 생각해 봐야겠다.

 

import sys

n = int(sys.stdin.readline())
cnt = 0
arr = []

if n == 1:
    cnt = 9

elif n > 1:
    for k in range(10 ** (n - 1), 10 ** n):
        for i in range(1,n+1):
            if i == 1:
                x = k % (10**i)
                arr.append(int(x))
            elif i == n:
                x = k / 10**(n-1)
                arr.append(int(x))
            else: 
                x = (k % (10**i))/(10**(i-1))
                arr.append(int(x))

        for z in range(len(arr)):
            try:
                if abs(arr[z] - arr[z + 1]) == 1:
                    cnt = cnt + 1
            except IndexError:
                pass
        arr = []




print(cnt)

자릿수를 직접 구해서 비교하는 알고리즘을 만들었으나 이것도 역시 시간 초과로 실패..

 

N = int(input())
dp = [[0]*10 for _ in range(N+1)]

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

MOD = 1000000000

for i in range(2, N+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[N]) % MOD)