문제

SuperSum 함수는 다음과 같이 정의된다.

  SuperSum(0,n)=n (n은  모든 양의 정수)

  SuperSum(k,n)=SuperSum(k−1,1)+SuperSum(k−1,2)+...+SuperSum(k−1,n)

k와 n이 여러개 주어진다. SuperSum의 값을 각각 출력하시오.

입력

k(1<=k<=14)와 n(1<=n<=14)이 입력된다. 입력의 끝은 EOF(End Of File)이다.

입력 예시

1 3
2 3
4 10
10 10

출력

SuperSum(k,n)의 값을 각 행에 하나씩 출력한다.

출력 예시

6
10
2002
167960

문제 풀이

메모제이션에서 시간이 너무 많이 쓰였다.
처음 문제를 접하고 풀때도 고민을 상당히 많이 했는데 그래도 과정이 어떻든 문제를 풀 수 있어서 다행이다.

일단 해당 문제를 접근하는 방식은 다음과 같았다.

(문제풀이 시 처음 사용해보는 아이패드!)

이를 바탕으로 여러가지 시도를 해서 문제를 풀었다.
일단 처음에 가장 어려웠던 건, 어떻게 EOF를 받아서 입력을 중단할 수 있을까였는데, 이건 찾아보니 금방 나왔다. (try, except 사용하면 쉬움)

메모제이션은 한번도 해본적이 없어서, 처음 구현할땐 정말 애를 먹었다.
사실 SuperSum 자체로만 진행을 했을때는 아래와 같이 코드를 작성하였다.

k가 0일때는, 그대로 n 값이 노출되어야하고, k가 0이 아닌 경우에는 재귀함수를 계속 돌려 0을 만들어주도록 코드를 작성하였다.

def SuperSum(k,n):
    sum = 0
    if k != 0:
        for i in range(1,n+1):
            sum += SuperSum(k-1,i)
        return sum
    elif k == 0:
        return n

메모제이션을 어떤식으로 넣을까 고민을 했는데, 대다수의 사람들이 dictionary형으로 문제를 많이 풀기도 했고, 내가 이해하기도 훨씬 수월해서 사용하였다.
처음에 key 값을 따로 정해두지 않고 superSum([k,n]) 과 방식으로 풀어보려고했는데, 그럴 경우에는 이후 해당 값이 supersum_memo에 들어있는지 확인하기가 너무 복잡해서 아예 처음부터 key값을 만들었다.

superSum_memo = {}

def SuperSum(k,n):
    key = f"{k},{n}"
    if k == 0:
        superSum_memo[key] = n
        return n
    if not key in superSum_memo:
        sum = 0
        for i in range(1,n+1):
            sum += SuperSum(k-1,i)
        superSum_memo[key] = sum
        return sum
    else:
        return superSum_memo[key]

number_list = []
while True:
    try:
        k,n = map(int,input().split(" "))
        number_list.append([k,n])
    except:
        break

for i in range(0,len(number_list)):
    print(SuperSum(number_list[i][0],number_list[i][1]))

진짜 3일은 투자한 것 같다.
중간에 포기하지 않고 문제를 푼 나 칭찬해!