최대 1 분 소요

9095번: 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의 합으로 나타내는 방법의 수를 출력한다.


첫 번째 시도 .

t = int(input())

for _ in range(t):
    d=[0]*11
    n = int(input())
    d[0]=1
    d[1]=2
    d[2]=4
    if n <= 3:
        print(d[n-1])
    else:
        for i in range(3,n):
            d[i] = d[i-1]+d[i-2]+d[i-3]
        print(d[n-1])

»intput

3
4
7
10

»output

7
44
274

success

image-20220222150652401


🌝 Thinking

9095

한 20분 동안 패드로 이래저래 생각해보다 점화식을 발견해냈다!!

오른쪽 끝에 앞선 세 항에서 부족한 값을 오른쪽에 더한다는 규칙을 생각한다면

왜 i 번째 항은 (i - 1), (i - 2), (i - 3)항들의 합인지 알 수 있다.



💡 깨달은 점.

  1. 점화식을 순수 머리속으로만 구현해낸다는 것은 정말 어렵다. 종이와 펜이 아직 필요한 단계지만 훈련을 많이 한다면 충분히 머릿속에서 점화식을 구상할 수 있을 것이다!!

댓글남기기

참고