[백준] 1, 2, 3 더하기 (9095번)

난이도 : Silver3
Link : https://www.acmicpc.net/problem/9095
Tag : 다이나믹 프로그래밍
풀이일자 : 2024년 9월 13일

📌 문제 탐색하기

N : 1, 2, 3으로 만들 정수
본 문제는 1, 2, 3으로 만들 수 있는 경우의 수를 구하는 문제이다.
순열과 조합으로 이 문제를 접근 가능하지만 순열을 구하는 과정에서 시간복잡도가 증가될 가능성이 있으므로 DP로 접근 가능하다.

가능한 시간복잡도

본래 구했던 경우의 수에서 추가되는 경우의 수를 구한다는 것이 DP의 기본적인 개념으로 시간복잡도는 O(n)으로 생각 할 수 있다.

📌 문제 접근 방법

DP를 사용해서 접근할 예정이다.
예를 들어
1을 만들 수 있는 경우의 수는 1 이렇게 1개이다.
2를 만들 수 있는 경우의 수는 1+1 , 2 이렇게 2개이다.
3을 만들 수 있는 경우의 수는 1+1+1, 1+2, 2+1, 3 이렇게 4개 이다.

다음 문제에서 조건이 1, 2, 3을 이용해서 N을 만드는 것이다.
따라서

4를 만들 수 있는 경우의 수는 위에서 구한 1, 2, 3을 만들 수 있는 경우의 수에서 1과 3을 이용하는 경우의 수, 1과 2를 이용하는 경우의 수를 더한 값과 같다.
따라서 4를 만들 수 있는 경우의 수는 7가지가 된다.

한번더 5까지 진행한다면
4에서 1을 더하는 방법 (7가지)
3에서 2를 더하는 방법 (6가지)
2에서 3을 더하는 방법
4와 1를 사용하는것 7가지 + 3과 2를 사용하는것 6가지를 더해 13가지가 된다.

따라서 점화식을 만든다면
N = N-1 + N-2 + N-3 이라고 볼 수 있다.

📌 코드 설계하기

1. 테스트 케이스 n을 입력받는다.
2. 1~3으로 만들 수 잇는 경우의 수를 arr[1], arr[2], arr[3] 에 저장한다.
3. for문을 통해 4~11까지 dp를 진행한다.
4. 들어오는 테스트 케이스의 결과값을 보여준다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())

arr = [0] * 11
arr[1] = 1 # 1을 만들 수 있는 경우의 수
arr[2] = 2 # 2를 만들 수 있는 경우의 수
arr[3] = 4 # 3을 만들 수 있는 경우의 수

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

for i in range(0,n):
    a = int(input())
    print(arr[a])