1,2,3 더하기

알고리즘 문제1

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

코드로 들어가기 전에 위 문제를 푸는 방식을 설명하자면

위 사진은 입력값을 줄여가면서 0에 도달한 트리(?),노드(?) 가짓 수를 계산 하는 방법이다.

반대로 T 값을 높이는 방법을 사용할수도 있다.

최종적으로 T=3일대 (1,1,1),(1,2),(2,1),(3) 4가지가 된다.

재귀적 풀이

count = 0

def cal(T):
  global count
  if 0 == T:	
      count += 1
      return 
  elif 0 > T :	
      return
  elif 0 < T :	
      cal(T-1)
      cal(T-2)
      cal(T-3) 

for i in range(int(input())):#횟수 입력
    count = 0	
    cal(int(input()))
    print(count)

위 사진을 코드로 풀어낸 모습니다.

1, 2, 3으로 수식을 풀어나가야 하기 때문에 cal() 을 재귀함으로서 값을 찾으면 된다