[python]백준 9095번 : 1,2,3 더하기

문제 : 백준 9095번 _ 1,2,3 더하기

https://www.acmicpc.net/problem/9095

나의 답

# 백준 9095번: 1,2,3 더하기
# 2020-02-01

case = int(input()) # 입력받기
num = []

def cpt_num(n):
    if n>3: # 3보다 크면
        return cpt_num(n-3) + cpt_num(n-2) + cpt_num(n-1)
    elif n==3: # 3이면
        return 4
    elif n==2: # 2이면
        return 2
    elif n==1: # 1이면
        return 1

while case :
    case-=1
    num.append(int(input()))

for n in num:
    print(cpt_num(n))

 어제 배웠던 다이나믹 프로그래밍을 활용하여 계산을 해보았다. 모든 경우의 수를 매겨야하는데 출력에 경우의 수에 해 당하는 값을 모두 출력하라는 말은 없어서 경우의 수만 구하면 되기 때문에 변수를 많이 쓸 필요가 없었다.

 함수 cpt_num(n)은 주어진 n에 대해서 몇 개의 경우의 수가 존재하는 지 계산하는 함수이다. 우선 해당 수가 3 이하인 경우에 1,2,3 일 때는 쉽게 직접 계산해서 1,2,4가지의 경우의 수가 나온다는 것을 알 수 있다. 따라서 주어진 수가 3이하인 경우를 나누고 3이상인 경우에는 1,2,3을 뺀 다음에 재귀적으로 다시 함수에 넣는다.

 ex_) 7을 함수에 넣으면 3보다 크므로 f(4)+f(5)+f(6) 이 return 값이다. 이에 따라 재귀적으로 f(4)는 f(1)+f(2)+f(3) 이런 식으로 다시 계산된다. 풀어쓰면 f(4)+f(5)+f(6)={f(1)+f(2)+f(3)}+{f(2)+f(3)+f(4)}+{f(3)+f(4)+f(5)}이다. 여기서 f(1),f(2),f(3)은 모두 상수로 return 되므로 f(4),f(5)를 재귀적으로 다시 계산하면 된다.

이 풀이법은 11이라는 작은 입력 범위 덕분에 가능한 방법이다. 재귀를 돌아서 계산하는 결과값이 따로 저장되어있지 않음으로 항상 다시 계산해야한다. 따라서 11번만 돌아도 3^11의 재귀를 돌게 된다. 3^11은 시간초과가 일어나지 않는 정도여서 괜찮지만 입력의 범위가 커지면 불가능하다. :)

 

다른 답

https://this-programmer.com/entry/%EB%B0%B1%EC%A4%809095%ED%8C%8C%EC%9D%B4%EC%8D%AC-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0

이 블로그에서는 본인과 같이 리스트에 계산한 수들을 넣고 앞의 3수의 계산값을 더하면 이번 index의 결과값이 된다는 규칙을 발견해서 풀었다. 하지만 리스트를 사용하여 결과값들을 저장해두고 다시 이용하였다.

 

배운 것

• 정해진 수의 나열은 리스트에 담아서 사용하는 것이 효과적이다.
• 동적 프로그래밍의 경우에는 문제의 기준에 맞는다면 재사용성을 고려할 수 있다면 좋다.