[BOJ] 2775번

https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

Python3

if __name__ == '__main__':
    test = int(input())

    for _ in range(test):
        K = int(input())
        N = int(input())
        floor = [i for i in range(1, N+1)]
        for k in range(K):
            for n in range(1, N):
                floor[n] += floor[n-1]
        print(floor[N-1])

testcase의 개수를 받은 후 개수만큼 거주민을 구했다.

3층	1	5	15	35	70
2층	1	4	10	20	35
1층	1	3	6	10	15
0층	1	2	3	4	5

위와 같이 거주민이 구성되는데 이를 잘보면 2층 4호라고 하면 2층 3호의 거주민과 1층 4호의 거주민의 합으로 구할 수 있다. 2층 4호 거주민은 1층 1호부터 1층 4호까지의 거주민의 합인데 1층 3호까지 거주민의 합이 2층 3호에 있으므로 2층 3호 + 1층 4호를 통해 구할 수 있는 것이다.

 

따라서 코드에서는 0번 층을 기준으로 배열을 만들고 거주민의 수가 1인 1호를 제외하여 1층부터 K층까지 N호의 거주민의 수를 구한다. 여기서는 1차원 배열을 이용하고 있기 때문에 이 배열에서 k층의 n호의 거주민의 수를 구하려면 floor[n] += floor[n-1]로 가능하다. floor[n-1]에는 k-1층의 1호부터 n-1호까지 거주민의 수가 저장되어있고, floor[n]에는 k-1층의 n호 거주민의 수가 저장되어 있기 때문이다. 거주민의 수가 다 구해지면 마지막 열에 있는 거주민의 수를 출력한다.