[알고리즘 문제] division (Python / 파이썬)

문제

임의의 자연수는 그보다 작은 자연수들의 합으로 표현될 수 있다. 예를 들어 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가 되는 식을 큰 숫자가 앞으로 오도록,

그리고 전체적으로도 앞의 숫자가 큰 식이 먼저 출력되도록 해야 합니다.

 

따라서 큰 숫자부터 1까지 하나씩 줄여가며 수를 넣어주어야 합니다.

이때, 만약 index가 0이라면 n-1 번째부터 시작해야하고

index가 0보다 크다면 n에서 지금까지 구한 합을 빼준 것부터 시작해야합니다.

 

시작 수부터 1까지 반복문을 수행하며 array를 채워 줍니다. 

큰 숫자가 앞으로 오도록 식을 구성해야 하므로 만약 더 큰 숫자가 뒤에 온다면

다른 숫자를 넣어주도록 해줍니다. 

지금 까지 구한 합에 넣어준 수를 더하고 다음 index 값을 넘겨주어 재귀를 실행해줍니다.

 

위의 과정대로 재귀를 실행하면 조건에 따라 식을 구할 수 있습니다.

만약 재귀를 수행하다가 구한 합이 입력한 수와 같아지면 식을 출력해줍니다.

그리고 식을 하나씩 출력할 때마다 count를 증가시켜 식의 수를 세어줍니다.

---

My Code

# 합이 n이 되는 식을 구하는 함수
def recur(mySum, index):
    global count 

    if mySum == n: # 구한 합이 n과 같아지면
        # 식을 출력
        print(array[0], end = '')
        for i in range(1, index):
            print('+' + str(array[i]), end = '')
        print() 
        # 식의 수를 세어 줌
        count += 1
    else:
        if index == 0:    # 첫 index라면 n-1부터 시작
            myNum = n - 1  
        else:             # n - mySum부터 시작 
            myNum = n - mySum 
        
        for i in range(myNum, 0, -1): # 큰 수부터 작은 수 순서로
            array[index] = i          # 배열에 넣어 줌

            # 더 큰 수가 뒤에 삽입되면 넘어감
            if index > 0 and array[index-1] < array[index]: continue

            # i를 더한 합과 다음 인덱스를 넘겨 재귀함수 수행
            recur(mySum + i, index + 1)
        
n = int(input()) # 구하고자 하는 합

array = [0] * 50
count = 0

recur(0, 0)
print(count)