[ 2023-03-07 🎩 TIL ]

백준 2775번

t는 들어오는 입력의 값의 갯수
k는 출력 할 아파트의 층, k층안에 있는 n번째 집

해당 문제에 나오는 아파트에 살 수 있는 규칙은 k층 n호 집에 살고 싶으면
k-1층에 1번째 집부터 n호 집까지 사는 사람의 합의 갯수와 동일한 수의 사람 만이 살 수 있습니다.

0층에 사는 사람은 n의 값과 동일한 사람이 살고 있음
=> 0층 1호 -> 1명, 0층 2호-> 2명, ... 14호 -> 14명 까지

k층 n번째에 사는 사람들의 수를 구하는 문제입니다.

import sys

input = sys.stdin.readline

t = int(input())
apt = [[n for n in range(1, 16)]] # 아파트 2차원 배열, 0층에 사는 사람은 넣어놨다.

if (t > 1):
    for i in range(1, 15):
        apt_li = [1 for _ in range(1, 16)] # 크기가 15인 배열 선언 0인덱스는 1
        for j in range(1, 15):
            apt_li[j] = apt_li[j-1] + apt[i-1][j]
        apt.append(apt_li)

for _ in range(t):
    k = int(input())
    n = int(input())
    print(apt[k][n-1])

해당 문제는 dp를 사용하여 풀었습니다.

이전 인덱스의 값과 이전 행에 동알 인덱스를 더하면 해당 값이 나옵니다.(팩토리얼 푸는 법과 거의 유사)

처음 자료구조를 시작했을 때 풀려고 시도했던 문제였는데 그때는 해결 못하고 넘어갔지만 오늘 해결한 것을 보니 공부를 했던것이 헛고생은 아니였다는 생각이 들어 뿌듯합니다. :)