mirae.kwak 2022. 3. 12. 01:30
728x90

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

 

2775번: 부녀회장이 될테야

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

www.acmicpc.net

 

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호 거주민의 수가 저장되어 있기 때문이다. 거주민의 수가 다 구해지면 마지막 열에 있는 거주민의 수를 출력한다.

728x90