BOJ : 2775 부녀회장이될테야

문제

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

2775번: 부녀회장이 될테야

풀이

처음에 이차원 배열을 통해 dp테이블을 생성하려고 했었으나...

 

그럴 필요가 없었고, 규칙을 잘보니 모든 층에 1호는 모두 1명이 산다는 것에서 힌트를 얻었습니다.

0층에 사는 사람들을 세팅해주고 이중 for문을 이용해 1층을 올라갈때마다 값을 계속해서 더해주면서 갱신해줍니다.

소스코드

import sys

t = int(sys.stdin.readline())

for _ in range(t) :
    #층
    k = int(sys.stdin.readline())

    #호수
    n = int(sys.stdin.readline())

    #0층 호수 별 사람 수
    v = [0] * (n)

    for i in range(n) :
        v[i] = i+1

    #1층을 올라가는 포문.
    for _ in range(k) :
        for j in range(1,n) :
            v[j] += v[j-1]
            
            

    print(v[-1])