백준 9095 123더하기 파이썬

백준 9095 123더하기 풀이

접근방식

1. 규칙성 찾기 -> 4일 경우 가능한 경우의 수 : 7 -> 7 = 1의 경우의 수 + 2의 경우의 수 + 3의 경우의 수 -> 결국, dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 이라는 규칙

# 입력받기
import sys

input = lambda: sys.stdin.readline().rstrip()

t = int(input())

test = list(map(int, (input() for _ in range(t))))

dp = [0 for _ in range(12)]

dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 12):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for num in test:
    print(dp[num])

해당 문제는 실버3레벨에 해당하므로 어렵지 않게 풀 수 있는 문제였습니다.

항상 다이나믹 프로그래밍은 규칙성을 도출하는 것이 핵심인데

이 문제는 그러한 규칙을 찾기에 아주 기초적인 문제로 적합했습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다. Just do it & Keep steady