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

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

 

 

목차

 

 

 

 

Python

 

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

 

우선 범주가 r, c는 50까지 설정할 수 있기 때문에 그 값이 커지는 점에 유의해야한다.

 

이 문제를 재귀로 풀 필요는 없다.

 

하지만 이를 재귀로 풀기 위해서는 memorization이 필요하고 이를 위한 2d list를 생성하여 저장한다.

 

그리고 만약 해당 위치에 값이 존재하면 저장된 list 값을 반환하여 사용한다. 

 

재귀로 돌릴 것은 현재 위치한 row와 column의 상태를 위해서는 row-1와 column의 value와 row와 column-1의 value를 더해야한다는 것에 착안하여 문제를 푸는 것이다.

 

pascal[row][column] = pascal[row-1][column] + pascal[row][column-1]

 

이 식을 재귀에 활용하는 방법을 잘 고민해보고 사용하자.

 

참조할 수 있는 문제

1. [CodeUp] 1930번 SuperSum

https://aigong.tistory.com/349

[CodeUp] 1930번 : SuperSum (Python)

 

def p(r, c, a):
  if r == 1 or c == 1:
    a[r-1][c-1] = 1
    return 1  
    
  if a[r-1][c-1]:
    return a[r-1][c-1]
  else:
    a[r-1][c-1] = p(r-1, c, a) + p(r, c-1, a)    
    return a[r-1][c-1]    

r, c = map(int, input().split())
a = [[0 for _ in range(c)] for _ in range(r)]
print((p(r,c,a) % 100000000))

 

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

파스칼의 삼각형이 대칭이라는 점에 착안하여 조금 더 많은 memorization이 가능하도록 하는 방안도 존재한다.

 

def p(r, c, a):
  if r == 1 or c == 1:
    a[r-1][c-1] = 1
    return 1  
    
  if a[r-1][c-1]:
    return a[r-1][c-1]
  else:
    a[r-1][c-1] = p(r-1, c, a) + p(r, c-1, a)    
    a[c-1][r-1] = a[r-1][c-1]
    return a[r-1][c-1]    

r, c = map(int, input().split())
a = [[0 for _ in range(50)] for _ in range(50)]
print((p(r,c,a) % 100000000))