백준 9095 1,2,3 더하기 문제풀이

문제 

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

9095번: 1, 2, 3 더하기

 

 

 

 

문제 접근 방식

n을 만들 수 있는 모든 경우의 수를 구하는 문제이고, 재귀함수를 활용한 백트래킹을 이용하여 모든 경우의 수에 접근할 수 있을 것으로 생각했다. 

 

시간 복잡도

정확한 경우의 수는 아니지만 최대 경우의 수 보다 큰 경우의수를 계산을 해서 어림해보는 방식으로 진행하려한다.

최대 항의 개수가 11이 될 수 있고, 각 항에 1,2,3 이 올  수 있다고 가정을 하면 이때의 경우의 수는 3^11 = 177147, 대략 1e6이다.

n 이 11일때의 경우의 수는 위에서 구한 경우의 수보다 무조건 경우의 수가 작을 수 밖에 없다. 즉, 최대 경우의 수 <= 1e6 이게 되므로 제한 시간을 만족한다.

 

 

코드

# dfs -> 현재 위치까지의 항들의 합이 주어질 때, n을 만들 수 있는 경우의 수를 반환하는 함수
def dfs(total):
    #total 값이 n 보다 크면 0을 반환하여 재귀함수를 종료한다.
    if total> n:
        return 0

    #total 값이 n 이라면 경우의 수 1을 추가해준다.
    elif total==n:
        return 1

    # 다음 항에 1,2,3 중 하나를 더해준다.
    answer=0
    for i in range(1,4):
        answer+=dfs(total+i)

    return answer


if __name__=='__main__':
    global n
    t=int(input())
    for _ in range(t):
        n=int(input())
        print(dfs(0))

 

회고

다른 분들은 어떻게 풀었나보니, 아래 규칙을 활용해서 문제를 풀었다.

A(n) = A(n-3)+A(n-2)+A(n-1) (n>=4)

 

1,2,4,7 이렇게 예시가 주어져서 이를 통해 위 식을 가정해볼 수 있고, 

입출력 예시의 n=7일 경우의 답이 44임이 나와있는 상태였기에 n=7을 대입해서 가정한 수식이 맞는지 확인하는 방향으로도 문제를 풀 수 있었을 것 같다.