백준 2775 python : 부녀회장이 될테야

 

오랜 시간의 고민 끝에, k층의 n호는, k-1층의 1호부터 n호까지의 합만큼의 인원이 산다는 것을 파악하였다.

그래서 재귀함수로 아래와 같은 코드를 짰는데, 시간 초과가 떴다.

 

1.재귀함수 이용

1) 1층과 2층 요소 출력을 위한 sigma 구현 공부

처음에 이 함수를 짜기 위해서, python 내에서 sigma를 정의하는 방법을 공부했다.

###sigma k : 1층의 n호 요소 출력하기

def sigma(n):
	result=0
    for k in range(1, n+1): #1부터 n까지
    	result +=k #1부터 n까지를 계속 더한다. 1+2+3+...+n
    return result

print(sigma(3)) #1층의 3호 요소 출력하기 : 1+2+3

###sigma k(k+1)/2 : 2층의 n호 요소 출력하기

def sigma2(n):
	result=0
    for i in range(1, n+1): #1부터 n까지
    	result += sigma(i)
    return result

print(sigma2(3)) #2층의 3호 요소 출력하기 : sigma(1)+ sigma(2) + sigma(3)

이렇게 계속 정의해 나가면 되겠지만, 입력 범위가 넓기 때문에 이렇게 계속 만드는 것은 불가능하다.

따라서 재귀함수로 만들어보고자 하여 아래와 같은 코드를 완성했다.

 

2) 재귀 함수 코드

import sys

input=sys.stdin.readline

T=int(input())
for _ in range(T):
    k=int(input()) #k층. 단계. sigma 횟수. 0층이 요소. 1층=1번 시그마, 2층=2번 시그마
    n=int(input()) #n호. 해당 시그마에서 n번까지 더해야함.
    
    def sigma_depth(k, n):
        if k==1: #초항 정의
            result=0
            for i in range(1, n+1): #i부터 n까지
                result +=i #다 더한다.1+2+...+n
            # print(k,'일 때 result=',result)
            return result
        else:
            result=0
            for i in range(1, n+1): #1부터 n까지
                result += sigma_depth(k-1, i) #아래층의 i까지의 합을 다 더한 것.
                # print(k,'일 때',i,'번째')
            # print(k,'일 때 result=',result)
            return result
            
	print(sigma_depth(k, n))

위 코드는 아래와 같은 원리로 정답이다.

그런데, 예시 1번에서는 계산이 얼마 되지 않아서 괜찮지만, 예시 2번부터는 굉장히 많은 계산이 이루어진다. 심지어 이미 계산했던 것들도 반복해서 계산해야하는 비효율적인 계산이 이루어진다.

=> 이를 행렬에 저장해놓고 인덱스로 가져다가 쓰는 방법으로 해결할 수 있을까 싶다. 인덱스의 시간 복잡도가 O(1)인 것을 확인하였다.

하지만 생각보다 복잡하다.

 

2. 간단한 점화식을 활용하여 계산하기

그래서 차분하게 써놓고 생각해보니

 matrix[k][n]=matrix[k-1][n]+matrix[k][n-1]과 같다.

그런데 결국 마지막 값만 출력하면 되기 때문에, 모든 층의 값들을 저장해둘 필요가 없다.

쉽게 생각하면 [바로 앞 호수 + 아래 층의 같은 호수]이기 때문에, 한 층을 한 호수씩 업데이트 해나간다고 생각하면 아래와 같이 코드를 간결하게 짤 수 있다.

 

import sys
input=sys.stdin.readline

t=int(input())

for _ in range(t):
	floor = int(input()) #층수
    num = int(input()) #호수
    f0 = [x for x in range(1, num+1): #0층 리스트. 1~n호까지
    for k in range(floor): #층 수 만큼 반복
    	for i in range(1, num): #1~n-1까지
        	f0[i] +=f0[i-1]
    print(f0[-1])

정답만 출력해내면 된다는 것을 기억하자.