[CodeUp] 1930번 : SuperSum (Python)

[CodeUp] 1930번 : SuperSum (Python)

 

 

 

목차

 

 

 

Python

일반적으로 생각한다면 다음과 같은 코드를 만들 수 있을 것입니다.

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

while True:
  try:
    k, n = map(int, input().split())
    print(super_sum(k,n))
  except:
    break

 

그러나 해당 방법은 자세히 보면 중복이 껴있다는 것을 확인하실 수 있습니다.

즉, memorization을 통해 시간을 줄여야한다는 것입니다.

이를 위해서 우리는 list로 저장하는 방법이 필요하고 이를 통한 값을 계산할 필요가 있습니다.

 

 

 

방법 1 - 메모리 27724 / 시간 27 / 코드 길이 464B

 

사용한 방법은 재귀를 통한 방법을 고집하기 위해 memorization을 사용한 것입니다. 이를 위해 list를 통해 값을 저장하도록 하였습니다.

다만 여기서 list의 index 설정에 어려움을 겪었는데 시간이 참 오래 걸릴 정도로 헷갈리는 것이 사실입니다.

 

def super_sum(k,n,b):
  if k==0:
    b[0][n-1]=n
    return n
  elif k !=0:    
    sum_k = 0 
    for i in range(n):
      if b[k-1][i]:
        sum_k += b[k-1][i]
      else:        
        t = super_sum(k-1, i+1, b)   
        sum_k += t
        b[k-1][i] = t    
    return sum_k

while True:
  try:
    k, n = map(int, input().split())
    a = [[0 for i in range(n)] for j in range(k)]    
    print(super_sum(k,n,a))
  except:
    break

 

 

방법 2 - 메모리 27724 / 시간 17 / 코드 길이 432B

 

해당 방법은 재귀를 포기하고 수학적 규칙을 활용한 방법입니다.

수학적 규칙에서는 다음과 같은 조화가 가능하기 때문에 이와 같이 구성해도 같은 답을 얻을 수 있습니다.

해당 내용은 파스칼의 삼각형(Pascal's triangle)과 유사하다고 판단되었고 이를 통한 방법을 활용한 방법입니다.

 

def super_sum(k,n,a):
  for i in range(n):
    a[0][i] = i+1
  for i in range(k):
    a[i][0] = 1

  for i in range(1, k):
    for j in range(1, n):
      a[i][j] = a[i][j-1] + a[i-1][j]

  s = 0
  for i in range(n):
    s += a[k-1][i]  
  return s
  

while True:
  try:
    k, n = map(int, input().split())
    a = [[0 for i in range(n)] for j in range(k)]    
    print(super_sum(k,n,a))
  except:
    break

 

더 발전된 문제를 풀고싶다면

CodeUp 3702 파스칼의 삼각형 문제 

https://aigong.tistory.com/351

[CodeUp] 3702번 : 파스칼의 삼각형 2 (Python)