boj_15992.md

BOJ 15992. 1,2,3 더하기 7

문제 링크

[BOJ 15992] 1,2,3 더하기 7

분류

다이나믹 프로그래밍

코드

import sys
input = sys.stdin.readline


def stop_plus(n: int, m: int):
    if n == 1:
        return plus[1][1]
    else:
        for y_idx in range(2, n+1):
            right_wall = min(y_idx, m)
            left_wall = max(2, right_wall // 3 - 1)
            for x_idx in range(left_wall, right_wall + 1):
                plus[y_idx][x_idx] = plus[y_idx - 3][x_idx - 1] + plus[y_idx - 2][x_idx - 1] + plus[y_idx - 1][x_idx - 1]

        return plus[n][m]


T = int(input())

plus = [[0 for _ in range(1001)] for _ in range(1001)]

# 하드코딩 파트
plus[1][1] = 1
plus[2][1] = 1
plus[3][1] = 1

input_list = []
max_N = max_M = 0

for _ in range(T):
    N, M = list(map(int, input().split()))
    input_list.append([N, M])
    max_N = max(max_N, N)
    max_M = max(max_M, M)

stop_plus(max_N, max_M)

for N, M in input_list:
    print(plus[N][M] % 1000000009)