코테 후기 - 재밌는 자연수 n의 합 종류 만들기

코테로 나온 4문제는 다풀었고, 보통 내가 풀려고 했던 문제까지 완성해서 제출하면 보통 후기를 쓰지 않지만 이번 4번 문제는 좀 획기적인 알고리즘 방법을 복습하고자 후기를 써본다.

 

문제는 이렇다.

자연수 n이 주어질 때 자연수 n을 만들 수 있는 합의 값은 여러가지가 있다.

n = 8일경우, 1+1+1+1+1+1+1+1, 2+1+1+1+1+1+1,... 등 많다.

이 자연수 n을 합의 종류를 만들고 그이후 여러가지 과정을 거치지만 그부분은 스킵하고 자연수 n만들기만 설명해보려고 합니다. 애초에 유명한 알고리즘이 있습니다.

 

# 풀이 절차 과정(함수 makePlusNums에 대한 설명)

1. 맨 처음 하나의 수를 리스트에 넣음.

2. 스택에 수를 꺼내면서 꺼낸 수 x가 1이 아니면 x-1를 스택에 넣음

2-1. 만약 x가 1이라면 스택에 1이 아닌 값이 나올때까지 계속 꺼내면서 (꺼낸 수들 1들의 합은 저장) 그러다가 1이 아닌수가 나오면 1이 아닌수를 y-1을 저장하고, 지금까지 합친 1의 합을 다시 리스트에 넣는다

3. 이를 모든 리스트들이 1로만 이루어질때까지 반복합니다.

 

이 풀이 과정의 근본적인 원리는 무엇일까요?

자연수 n = 8이 들어올때 값을 꺼내면서 -1을 해주면서 쪼개면서 합들의 합을 구하는 방식입니다.

 

개인적으로 풀이 절차 과정을 보시고 코드를 보신다음 이 코드 부분은 왜있는거지 라는 의문이 들면 그림을 참고해보시는 것을 추천드립니다.

 

 

코드 추가 설명

def makePlusNums(n):
    number = [n]
    ans = []

    while True:
        ans.append(number.copy())
        tmp = number.pop()
        if tmp != 1:
            number.append(tmp - 1)
            number.append(1)
        else:
            base = 2
            for _ in range(len(number)):
                if number and number[-1] == 1:
                    base += 1
                    number.pop()
            if not number:
                break

            pivot = number.pop() - 1
            number.append(pivot)
            while base > pivot:
                number.append(pivot)
                base -= pivot
            number.append(base)
    return ans


n = 5
print(makePlusNums(n))
# [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

---

후기

 

재밌는 알고리즘 풀이를 알게되서 재밌었다.