백준)부녀회장이 될테야

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

 

2775번: 부녀회장이 될테야

 

 

 

a = int(input())

for _ in range(a):
  n_arr = [i for i in range(1,15)]

  floor = int(input())
  ho = int(input())

  for i in range(floor):
    for j in range(14):
      zz = sum(n_arr[:j+1])
      n_arr.append(zz)

    n_arr = n_arr[14:]

  print(n_arr[ho-1])

문제를 보는 순간 어떻게 풀어야 할지 감도 잡히지 않았다.

아는 것이라고는 DP를 이용한다는 것.

고민하던 끝에 제한사항을 보고 깨달았다.

우선 한 층당 최대 호는 14호이다.

0층의 i호는 i명이 사니까,

0츠 14호는 14명.

1층 2호에는 0층의 1호 + 0층의 2호

2층의 2호에는 1층의 1호 + 1층의 2호...

 

이렇게 글로 적다보니 DP로 풀 수도 있을것 같긴 하다.