저주의 숫자 3, 쉬운 계단 수

저주의 숫자 3

저주의 숫자 3
프로그래머스 LEVEL 0
조건:
3의 배수와 숫자 3을 사용하지 않는다.

풀이:
n만큼 for문을 돌면서
3을 포함하거나 3의 배수인 경우에는 + 1 한다.
증가한 숫자가 저주의 숫자인 경우도 검사하기 위해
while 문을 사용

def solution(n):
    i = 0
    for _ in range(n):
        i += 1
        while i % 3 == 0 or '3' in str(i):
            i += 1
    return i

---

10844: 쉬운 계단 수

아이디어

• 점화식, 2차원 DP 테이블
• DP 테이블: dp[자리수][해당 자리에서 가장 뒤에 오는 숫자] = 경우의 수
• 점화식의 세분화
  • 가장 뒤에 오는 숫자 = 0)
    • 0 앞에 올 수 있는 건 1 하나 뿐이다. dp[자릿수][0] = 1
      
  • 가장 뒤에 오는 숫자 = 1~8)
    • dp[자리수][가장 뒤에 오는 숫자] = dp[자리수-1][가장 뒤에 오는 숫자-1] + dp[자리수-1][가장 뒤에 오는 숫자+1]
  • 가장 뒤에 오는 숫자 = 9)
    • dp[자리수][9] = 1
    • 9 앞에 올 수 있는 건 8 하나 뿐이다.

# 1일 1백준
import sys
n = int(sys.stdin.readline())

# dp 테이블 초기화
dp = [[0]*10 for _ in range(n+1)]

# 1의 자릿수의 경우 초기화
for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif 1 <= j <= 8:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
        else:
            dp[i][j] = dp[i-1][8]
print(sum(dp[n]) % 10**9)