[백준] 2775번: 부녀회장이 될테야 - 파이썬

🧩문제 해석

a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야한다.
k와 n이 주어질때 k층의 n호에는 몇 명이 살고 있는지 출력하면 된다.

층은 0층부터 있지만 입력 범위는 1 <= k,n <= 14 이다. 즉 0층은 주어지지 않는다.

 

📕 풀이

위로 올라갈수록 더하기만 주구장창 해주면 된다ㅎ

이제 각 층에 몇명이 살고 있는지 표로 살펴보자.

 

2층	1	4 (1+3)	10 (1+3+6)	아래층 전부 더한 값
1층	1	3 (1+2)	6 (1+2+3)	n까지의 합
0층	1	2	3	n
	1호	2호	3호	n호

 

이때 n층의 k호의 몇 명이 사는지 구하는 방법은 두가지 정도가 있다.

문제에서 주어진 것처럼 자신의 아래 층의 1호부터 n호까지의 합을 구할 수도 있고, 아니면 자신의 층의 (n-1)호에 자신의 아래층 n호를 더하여 구할 수도 있다. 

와따시는 전자로 답을 구했다. 그리고 후자는 글을 작성하다 보니 떠올랐다ㅎㅎ

 

💻 코드

import sys
input = sys.stdin.readline

for t in range(int(input())): # 테스트 케이스
    k= int(input().rstrip()) # 층 입력받음
    n = int(input().rstrip()) # 호 입력받음
    arr = [num for num in range(1, n+1)] # 0층에 사는 친구
    for i in range(k):
        new = [] # 값 담아줄 임시 저장소
        for j in range(n):
            new.append(sum(arr[:j+1])) # n호까지의 합을 더하여 new에 추가
        arr= new.copy() # arr로 반환해줌 위 과정을 k층까지 반복
    print(arr[-1]) # k층의 n호 값 출력

 

🔗 문제 링크 : 부녀회장이 될테야

2775번: 부녀회장이 될테야

 

python