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

 

📚 1, 2, 3 더하기

 

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

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

 

 

입력

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

 

출력

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

 

 

예제 입력 1 복사

3
4
7
10

 

예제 출력 1 복사

7
44
274

 

 

 

✍ 접근

• 피보나치 수열이라는 문제 제목부터 DP
• 피보나치 수열은 n = n-1 + n-2 라는 것을 알고 있으면 풀기 수월하다

 

 

정답 코드

import sys
input = sys.stdin.readline

T = int(input())

dy=[0,1,2,4]
def dynamic(n):
    if n<len(dy):
        return
    if n>3 and n >=len(dy):
        for i in range(len(dy),n+1):
            dy.append(dy[i-1]+dy[i-2]+dy[i-3])
        return

for _ in range(T):
    n = int(input())
    dynamic(n)
    print(dy[n])

 

• 피보나치 함수와 같은 방식으로 풀면 된다
  <핵심 키워드>
  
  1. DP의 memoization의 방법을 활용한다 : dy
• 테스트 케이스를 돌려 n을 찾을 때마다 dynamic이라는 함수를 실행시켜준다
  
  • 만약 n이 dy의 길이 안에 존재한다면 == 이미 갚이 구해진 상태라면
    => 그냥 return한다
  • n이 3보다 큰 경우(어차피 len(dy) 안에 있는 경우이기 때문에 필요 없는 제한이었다) & dy 배열의 길이를 넘어간 n의 값이 들어올 경우는
    => dy의 길이부터 n+1까지(n을 포함시키기 위해)for문을 돌면서 점화식을 시행해준다
• 점화식
  이 DP문제의 규칙을 찾기 위해 한번 손코딩을 해보자
  ❓ n = 1일 때 1 => 1개
  ❓ n = 2일 때 1+1, 2 => 2개
  ❓ n = 3일 때 1+1+1, 2+1, 1+2, 3 => 4개
  ❓ n = 4일 때 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3 => 7개
  ❓ n이 5일 때는 13개가 나온다
  
  규칙을 찾으면 n-3+n-2+n-1 => n의 개수가 된다
   

⭐ 배움

• 역시 규칙을 잘 찾는 게 중요하다!
• 규칙 찾기가 어려우면 하나하나 손으로 써내려가보자 🏹