[Baekjoon] 15990/1,2,3 더하기 5/Python/파이썬/다이나믹 프로그래밍

井·2025년 1월 21일

DP python 다이나믹프로그래밍 백준 알고리즘 파이썬

문제풀이

목록 보기

21/56

💡문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제입력

예제출력

3
9
27

📖내가 작성한 Code

import sys

'''
문제 요약
1,2,3의 합으로 나타내는 방법의 수
단, 같은 수를 두 번 연속 사용 금지
전형적인 DP 문제
'''

class Combination_Of_Number:
    def __init__(self):
        self.CURRENT_NUMBER = 3
        self.MAX_NUMBER = 100000
        self.MOD = 1000000009
        self.combination_list = [[0, 0, 0] for _ in range(self.MAX_NUMBER + 1)]
        self.combination_list[1] = [1, 0, 0]
        self.combination_list[2] = [0, 1, 0]
        self.combination_list[3] = [1, 1, 1]

    def renewal_max_nuber(self, number):
        for num in range(self.CURRENT_NUMBER + 1, number + 1):
            self.combination_list[num][0] = (self.combination_list[num - 1][1] + self.combination_list[num - 1][2]) % self.MOD
            self.combination_list[num][1] = (self.combination_list[num - 2][0] + self.combination_list[num - 2][2]) % self.MOD
            self.combination_list[num][2] = (self.combination_list[num - 3][0] + self.combination_list[num - 3][1]) % self.MOD
        self.CURRENT_NUMBER = number

def main():
    speed_input = sys.stdin.readline
    new_combination_of_number = Combination_Of_Number()
    for _ in range(int(speed_input())):
        number = int(speed_input())
        if new_combination_of_number.CURRENT_NUMBER < number:
            new_combination_of_number.renewal_max_nuber(number)
        print(sum(new_combination_of_number.combination_list[number]) % new_combination_of_number.MOD)

if __name__ == '__main__':
    main()

✍️풀이과정

다른 DP 문제와 마찬가지로 숫자에 1,2,3 더하는 3가지 유형으로 분해해봤음. 그런데, 항상 max값까지 계산하기 보다는 동적으로 계산 해보는 게 어떨까해서 클래스로 구성해봄. 결과론 적이고, 메모리 사용 및 초기화 시간은 효율적이나, 코드 복잡성이 증가하였다. AI는 N이 작은 경우는 전체 DP를 사용하는 것을 추천하고, N이 매우 크거나, 여러 테스트 케이스가 다양한 범위의 N을 요구하는 경우에만 동적으로 해라고 추천함.

🧠 코드 리뷰

메서드 이름 오타 수정: renewal_max_nuber는 renewal_max_number로 수정하는 것이 좋습니다. 오타는 코드의 가독성을 저해할 수 있습니다.
초기화 범위 최적화: combination_list를 처음부터 MAX_NUMBER까지 초기화하지 않고, 필요한 만큼만 확장하는 방식으로 변경할 수 있습니다. 이는 메모리 사용을 더욱 최적화할 수 있습니다.
입력 처리 최적화: 여러 개의 입력을 한 번에 읽고 처리하는 방식으로 성능을 더 향상시킬 수 있습니다. 예를 들어, sys.stdin.read()를 사용하여 모든 입력을 한 번에 읽은 후, 이를 분리하여 처리하는 방식입니다.
클래스 사용의 필요성 재고: 클래스 사용은 코드의 구조화와 재사용성 측면에서 유리할 수 있지만, 단순한 DP 문제에서는 함수 기반 접근 방식이 더 간결할 수 있습니다. 이는 개인의 선호에 따라 다를 수 있습니다.
메모리 최적화: combination_list의 각 항목을 [0, 0, 0] 리스트 대신 튜플로 저장하여 약간의 메모리 사용을 줄일 수 있습니다. 다만, 이는 가독성에 영향을 줄 수 있습니다.

🛠️AI 개선 코드

import sys
from typing import List

'''
문제 요약
1, 2, 3의 합으로 나타내는 방법의 수
단, 같은 수를 두 번 연속 사용 금지
전형적인 DP 문제
'''

class CombinationOfNumber:
    def __init__(self):
        self.MOD: int = 1000000009
        # 초기화 범위를 최소화하고, 필요한 만큼만 확장
        self.combination_list: List[List[int]] = [
            [0, 0, 0] for _ in range(4)  # 인덱스 0부터 3까지 초기화
        ]
        self.combination_list[1] = [1, 0, 0]  # 마지막 수가 1인 경우
        self.combination_list[2] = [0, 1, 0]  # 마지막 수가 2인 경우
        self.combination_list[3] = [1, 1, 1]  # 마지막 수가 1, 2, 3인 경우
        self.current_max: int = 3

    def extend_combinations(self, number: int) -> None:
        """
        DP 테이블을 number까지 확장합니다.
        """
        if self.current_max >= number:
            return
        for num in range(self.current_max + 1, number + 1):
            # 필요 시 combination_list 확장
            if num >= len(self.combination_list):
                self.combination_list.append([0, 0, 0])
            # DP 상태 업데이트
            self.combination_list[num][0] = (
                self.combination_list[num - 1][1] + self.combination_list[num - 1][2]
            ) % self.MOD
            self.combination_list[num][1] = (
                self.combination_list[num - 2][0] + self.combination_list[num - 2][2]
            ) % self.MOD
            self.combination_list[num][2] = (
                self.combination_list[num - 3][0] + self.combination_list[num - 3][1]
            ) % self.MOD
        self.current_max = number

def main():
    input_data: List[str] = sys.stdin.read().split()
    T: int = int(input_data[0])
    queries: List[int] = list(map(int, input_data[1:T+1]))
    
    max_query: int = max(queries) if queries else 0
    combination = CombinationOfNumber()
    combination.extend_combinations(max_query)
    
    results: List[str] = []
    for number in queries:
        if number <= 0:
            results.append("0")
            continue
        total = (
            combination.combination_list[number][0] +
            combination.combination_list[number][1] +
            combination.combination_list[number][2]
        ) % combination.MOD
        results.append(str(total))
    
    print('\n'.join(results))

if __name__ == '__main__':
    main()