백준 알고리즘 2775 (부녀회장이 될테야) - python

[문제] 백준 알고리즘 2775 (부녀회장이 될테야) - python

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

2775번: 부녀회장이 될테야

 

a층 b호에 사는 자신의 아래층(a-1)에 사는 b호 까지의 모든 사람의 합을 구하는 문제.

규칙을 찾기 보다는, 2차원 배열로 누적하면 간단해지는 문제라고 생각이 들었다.

 

먼저, 0층에는 b호에 b명이 산다고 보면 된다. 그리고 어느 층에도 1호는 1명이 산다.

그리고 나머지는 문제에 나온 대로 누적해보면 답이 나온다.

따라서, 0층을 먼저 구현해놓고, 1호는 항상 1인 층을 스택하면서 2차원 배열을 만든다.

코드로 만들 때는 한 층을 담당하는 임시 배열(tmp)을 만들고,

전체 배열(apt)에서 아래 층의 b호 까지의 값을 더한 값들을 다시 전체 배열(apt)에 누적해 나가다가

k층 n호까지 만들고 출력하면 끝이다.

 

[Code]

T = int(input())
for _ in range(T):
    k = int(input())
    n = int(input())
    apt = [[i for i in range(1, n+1)]] # 0층
    for i in range(1, k+1): # 1층부터 k층
        tmp = [1] # 1호
        for j in range(2, n+1): # 2호부터 n호
            tmp.append(sum(apt[i-1][:j]))
        apt.append(tmp)
    print(apt[-1][-1])