[파이썬 알고리즘] 백준-9095- 1,2,3 더하기

 

처음에 풀 때는 5까지 구해보고 풀어봤다.

•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), (1 + 1 + 2), (1 + 2+ 1), (1 + 3), (2 + 1 + 1), (2 + 2), (3 + 1)  

7개  

• n = 5 -> (1 + 1 + 1 + 1 + 1), (1 + 1 + 1 + 2), (1 + 1 + 2 + 1), (1 + 1 + 3), (1 + 2 + 1 + 1), (2+ 1 + 1 + 1), (1 + 2 + 2), (2 + 1 + 2), (2 + 2 + 1), (1 + 3 + 1), (3 + 1 + 1), (2 + 3), (3 + 2)

13개

 

그랬더니 규칙이 보였다.

바로 1+2+ 4 = 7 , 2+ 4 + 7 = 13

그래서 바로 코드로 가서 풀었다.

T = int(input())


def sum(n):
    if n == 1:
        return 1

    elif n == 2:
        return 2

    elif n == 3:
        return 4

    else:
        return sum(n - 1) + sum(n - 2) + sum(n - 3)


for i in range(T):
    n = int(input())
    print(sum(n))

그러고 나서 다른 코드를 보다가 오늘 배운 백트래킹 개념이 나와서 이것도 참고했다.

T = int(input())


def bt(value, sum):
    global count      #전역 변수 global
    if sum >= n:      # 1,2,3을 더하는 가지를 치는데 sum을 초과하면 더이상 진행 x
        return
    sum += value
    if sum == n:
        count += 1
    bt(1, sum)
    bt(2, sum)
    bt(3, sum)


for i in range(T):
    n = int(input())
    count = 0
    bt(0, 0)
    print(count)

 

이 코드 같은 경우에는 backtracking을 사용해서 풀었는데 코드만 보고 이해하기 어려워서 직접 그려서 표현해 봤다.

이런 식으로 가지치기하다가 sum >= n이면 백 트래킹 하여 그 부분을 들어가지 않는다.