1. 문제이해

• 정수 n을 1, 2, 3의 합으로 나타내는 방법의 경우의 수를 구해야 함
• n은 11보다 작은 양수

2. 접근방법-bottom up

1. 작은 n에 대한 해답을 미리 초기화
   1. 1을 만드는 방법: 1가지(1)
   2. 2를 만드는 방법:2가지 (1+1, 2)
   3. 3을 만드는 방법:4가지(1+1+1, 1+2, 2+1, 3)
2. 큰 n에 대한 해답은 작은 n들의 해답을 이용하여 계산하는 방법임
3. 점화식: f(n) = f(n-1) + f(n-2) + f(n-3)
   • n을 만드는 방법 = (n-1을 만든 후 1을 더하는 방법) + (n-2를 만든 후 2를 더하는 방법) + (n-3을 만든 후 3을 더하는 방법)

2-1) 코드 구현

T=int(input())

for _ in range(T):
    n=int(input())

    cache=[0]*12
    cache[1]=1
    cache[2]=2
    cache[3]=4

    for i in range(4,n+1):
        
        cache[i]=cache[i-1]+cache[i-2]+cache[i-3]
    print(cache[n])

3.접근방식-top down

• 재귀 함수 사용
• 메모이제이션으로 중복 계산 방지
  • 이전에 계산한 결과를 저장하고 재사용하는 기법 (코드에선 리스트로 캐시 구현하여 연산결과 저장)

메인 로직

• 테스트 케이스 수 T 입력
• 각 테스트 케이스마다:
  • n 입력
  • cache 배열 초기화 (크기 12)
  • count(n, cache) 호출 및 결과 출력
• count함수
  • 처음 구하는부분, 이미 구했던 부분으로 나누어서 함수 구성

3-1)코드 구현

T=int(input())

def count(n,cache):
		
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    #이미 계산한 값이 있을 경우
    if cache[n] !=0:
        return cache[n]
    
	  #새롭게 계산해야하는 경우 
    cache[n]=count(n-1,cache)+count(n-2,cache)+count(n-3,cache)
    return cache[n]
    

for _ in range(T):
    n=int(input())

    cache=[0]*12

    print(count(n,cache))

두 방식의 차이점 정리

1. 계산 순서
   • Bottom-up: 작은 문제부터 큰 문제로 순차적 계산
   • Top-down: 큰 문제에서 시작해 작은 문제로 분할하여 계산
2. 메모리 사용
   • Bottom-up: 모든 부분 문제의 결과를 저장
   • Top-down: 필요한 부분 문제의 결과만 저장 (메모이제이션)
3. 구현 방식
   • Bottom-up: 반복문 사용
   • Top-down: 재귀 함수 사용
4. 계산 효율성
   • Bottom-up: 모든 부분 문제를 한 번씩 계산
   • Top-down: 필요한 부분 문제만 계산 (불필요한 계산 회피 가능)
5. 코드 구조
   • Bottom-up: 테이블을 미리 초기화하고 순차적으로 채움
   • Top-down: 재귀 호출 시 결과를 캐시에 저장