[파이썬] 2775 : 부녀회장이 될테야

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

제한

• 1 ≤ k, n ≤ 14

예제 입력 1 복사

2

1

3

2

3

예제 출력 1 복사

6 10

정답

#재귀
def cntPerson(k,n):
    if k==0:
        return n
    s=0
    for i in range(1, n+1):
        s += cntPerson(k-1, i)
    return s

for i in range(int(input())):
    k=int(input())
    n=int(input())
    print(cntPerson(k, n))

첫번째. 재귀 방법이다.

함수 cntPerson에 구하려는 k층과 n호를 넣는다.

 

함수 cntPerson을 한번 거칠때마다 k-1층의 n호까지의 인원 수의 합을 구하게 된다.

 

예를들어, 2층(k=2) 4호(n=4) 의 인원을 구한다고 해보자.

 

k = 2
n = 4
s = 0

   cntPerson(2, 4)
for문이 1부터 5미만까지 돌게 됨.
s = cntPerson(1, 1) + cntPerson(1, 2) + cntPerson(1, 3) + cntPerson(1, 4)

cntPerson(1, 1) = cntPerson(0, 1) = 1
cntPerson(1, 2) = cntPerson(0, 1) + cntPerson(0, 2) = 1 + 2 = 3
cntPerson(1, 3) = cntPerson(0, 1) + cntPerson(0, 2) + cntPerson(0, 3) = 1 + 2 + 3 = 6
cntPerson(1, 4) = cntPerson(0, 1) + cntPerson(0, 2) + cntPerson(0, 3) + cntPerson(0, 4) = 1 + 2 + 3 + 4 = 10

s = 1 + 3 + 6 + 10 = 20(명)

재귀를 사용하면 위의 방법으로 계산을 하게 된다.

그리고 다른 방법도 있다.

 

#반복문
for i in range(int(input())):
    k = int(input())
    n = int(input())
    l = [i for i in range(1, n+1)]
    for _ in range(k):
        for j in range(1, n):
            l[j] += l[j-1]
    print(l[n-1])

두번째. 반복문

3중 포문이 돌아가게 되며, 결국 n호의 인원수를 구하기 위해선, 아래층에 n호만 있으면 된다.

따라서 for문을 k번 돌려서 맨아래층의 각 호수별 주민 수 list를 갱신하는 방식으로 list 안의 요소를 구한다.

 

list가 0부터 시작하고, 호수는 1호부터 시작하므로, 마지막 출력시 리스트 인덱스 출력에 주의하자.

 

---

다만 위 두가지 방법에 있어 주의해야될것이 있다.

아래가 재귀, 위가 반복문

재귀의 경우, 반복문에 비해 소요시간이 굉장히 긴 것을 알 수 있다.

따라서 들어가는 값의 범위등을 고려하여 알고리즘을 짤때 시간복잡도를 계산해보는게 좋을 거 같다.

 

아니면, 기존 python에서는 재귀의 경우, 시간 초과가 날 수 있는데 pypy3를 사용하면 시간초과가 안날수도있으니 python에서 시간초과가 난다면 pypy3로 다시 시도해보자.