[Algorithm 풀이] 재귀 함수 : division

 

문제

임의의 자연수는 그보다 작은 자연수들의 합으로 표현될 수 있다. 예를 들어 4의 경우,

4
= 3+1
= 2+2
= 2+1+1
= 1+1+1+1

위와 같은 방법으로 표현 될 수 있다. 이 때 , 숫자의 구성이 같으면서 그 순서만이 다른 경우는 같은 경우로 생각하는데, 예를 들어 다음 세 가지 경우는 모두 같은 경우이다.

2 + 1 + 1, 1 + 2 + 1 , 1 + 1 + 2

자연수 n을 입력 받아 이를 n보다 작은 자연수들의 합으로 나타내는 방법을 모두 출력하는 프로그램을 재귀 호출을 사용하여 작성하시오.

---

입력

첫 줄에 2 이상 20 이하의 자연수 n이 주어진다.

---

출력

첫째 줄부터 모든 방법을 한 줄에 하나씩 출력한다. 하나의 식 안에는 큰 숫자가 앞으로 오도록 하고, 전체적으로는 앞의 숫자가 큰 식이 먼저 출력되도록 한다. 숫자와 더하기 사이에는 공백이 없다. 그리고 마지막 줄에는 나누어진 자연수의 개수를 출력한다.

---

예제 입력

5

예제 출력

4+1

3+2

3+1+1

2+2+1

2+1+1+1

1+1+1+1+1

6

---

CODE

## template
def getResult(mySum, index, n, result):
  if mySum == n:
    print(result[0], end='+')
    for i in range(1, index):
      if i == index-1:
        print(result[i], end='')
      else:
        print(result[i],end='+')
    print() 
    global cnt
    cnt+=1
  
  else:
    if index == 0:
      myNumber = n-1
    else:
      myNumber = n - mySum
      
    for i in range(myNumber,0,-1):
      result[index] = i
      if (index > 0) and (result[index-1] < result[index]):
        continue
      getResult(mySum+i, index+1, n, result)
  return cnt

if __name__ == '__main__':
  n = int(input())
  cnt = 0
  result = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  print(getResult(0, 0, n, result))

 

⭐️ SOLUTION

1. 큰수부터 작은 수 순서대로 (중복제거 = 숫자가 커지면 안됌)

2. 현재까지 구한 합이 mySum, index 번째 숫자를 결정하여 출력

  #현재까지 구한 합이 mySum
  #지금, index 번째 숫자를 결정할 차례. 즉, result[index]
  if mySum == n:
    print(result[0], end='+')
    for i in range(1, index):
      if i == index-1:
        print(result[i], end='')
      else:
        print(result[i],end='+')
    print() 
    global cnt # 갯수 출력
    cnt+=1

3. mySum 이 n 이 아닐 경우 처리

  else:
    if index == 0:
      myNumber = n-1
    else:
      myNumber = n - mySum
      
    for i in range(myNumber,0,-1):
      result[index] = i #result에 요소를 하나씩 감소하여 넣기
      if (index > 0) and (result[index-1] < result[index]): 
        continue
      getResult(mySum+i, index+1, n, result) #재귀호출