[CodeTree/Python] 앞의 두 수를 더한 수열, 1, 2, 3 더하기

문제

앞의 두 수를 더한 수열

첫 번째 항이 0이고, 두 번째 항이 1인 수열이 있습니다.

이 수열의 세 번째 항부터는 바로 앞의 두 항의 합을 값으로 가집니다.

n이 주어졌을 때, 이 수열에서 n + 1 번째 항을 구하는 프로그램을 작성하세요.

 

입력 형식

첫 번째 줄에 정수 n이 주어집니다.

• 1 ≤ n ≤ 20

출력 형식

첫 번째 줄에 n + 1 번째 항을 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이

n = int(input())

li = [0, 1]
def func(n):
    while True:
        for i in range(len(li)):
            li.append(li[len(li) - 2] + li[len(li) - 1])
            if i == n:
                return li[n]


print(func(n))

1. 첫 번째 항과 두 번째 항이 주어진다.
2. while문을 돌면서 앞의 두 항의 합계값을 추가한다.
3. i가 n과 같아지면, 합계값을 리턴한다.

  왜 백트래킹 문제인지는 잘 모르겠음 ..

---

문제

1, 2, 3 더하기

정수 n 을 1, 2, 3 의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하세요.

단, 합을 나타낼 때는 숫자를 1개 이상 사용해야 합니다.

예를 들어 4는 다음과 같이 7가지 방법으로 나타낼 수 있습니다.

 

입력 형식

첫 번째 줄에 정수 n 이 주어집니다.

• 1 ≤ n ≤ 11

출력 형식

n 을 1, 2, 3의 합으로 나타내는 방법의 수를 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이

'''
a[1] = 1
a[2] = 2
a[3] = 4
a[4] = 7
a[5] = 13
a[6] = 24
...
a[n] = a[n-1] + a[n-2] + a[n-3]
'''

n = int(input())
d = [0 for _ in range(3 + n)]
d[0] = 0
d[1] = 1
d[2] = 2
d[3] = 4
for i in range(n + 1):
    if i > 3:
        d[i] = d[i - 1] + d[i - 2] + d[i - 3]

print(d[n])

    위 문제와 동일한 방식으로 해결하였다.