🏄‍♀️ 코딩테스트/🐍 Python

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

Po_tta_tt0 2022. 6. 3. 12:59
반응형

 

📚 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의 개수가 된다
     

⭐ 배움

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