[백준] #1562 Python🤯

백준 1562번 파이썬

https://www.acmicpc.net/problem/1562

아이디어

1. 계단 수의 모든 경우의 수를 계산하고 담기엔 메모리 초과가 나므로 DP 이용
2. 0~9까지 숫자의 방문 미방문 처리를 표현하기 위해서 비트마스크 이용

전체코드

출처: https://hddcp.tistory.com/18

n = int(input())
 
re = 0
dp = [[0 for _ in range(1024)] for _ in range(10)]
 
for i in range(1, 10):
    dp[i][1<<i] = 1
 
for i in range(1, n):
    dp_next = [[0 for _ in range(1024)] for _ in range(10)]
    for e in range(10):
        for bm in range(1024):
            if e < 9:
                dp_next[e][bm | (1<<e)] = (dp_next[e][bm | (1<<e)] + dp[e+1][bm]) % 1000000000
            if e > 0:
                dp_next[e][bm | (1<<e)] = (dp_next[e][bm | (1<<e)] + dp[e-1][bm]) % 1000000000
    dp = dp_next
 
print(sum([dp[i][1023] for i in range(10)]) % 1000000000)

어떤 방식으로 돌아가는 지는 알 것 같다,,, 하지만 아직 자세하게 코드를 이해하는 데에는 어려움이 있는 것 같다.

전체코드(내 코드 - 메모리 초과😩)

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

def level_num(queue):
    ans_ele = 0
    while len(queue) > 0:
        num, pos, bit = queue.popleft()
        if pos == N: 
            if bit == (1<<10) - 1:
                ans_ele += 1
            continue
        if 1 <= num <= 8:
            pos += 1
            bit1 = bit | (1<<num-1)
            bit2 = bit | (1<<num+1)
            queue.append([num-1, pos, bit1])
            queue.append([num+1, pos, bit2])
        elif num == 0:
            pos += 1
            bit = bit | (1<<num+1)
            queue.append([num+1, pos, bit])
        else:
            pos += 1
            bit = bit | (1<<num-1)
            queue.append([num-1, pos, bit])

    return ans_ele % 1000000000


ans = 0
if N < 10:
    print(ans)
else:
    for i in range(1, 10):
        queue = deque([(i, 1, (1<<i))])
        ans += level_num(queue)

    ans = ans % 1000000000
    print(ans)

BFS로 전체 경우의 수를 다 보려고 했다,,, 사실 dp보다는 훨씬 간단한 로직 구조이지만 공간 복잡도가 현저히 높아서 틀린 것 같다.

느낀점

공간 복잡도나 시간 복잡도 면에서 dp를 사용하기엔 유리한 경우엔 무조건 쓰는 것이 좋아 보인다. "sub problem -> problem" 잊지 말고 dp에 대해 더 디피 공부해야겠다.