2775. 부녀회장이 될테야

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 본문

접근 과정

• 아파트 a층의 b호에 거주하려면 a - 1층의 1호부터 b호까지의 거주자의 합만큼의 사람이 필요하다.

  • 2층의 3호 거주자는 1층의 1호부터 3호까지 거주자의 합만큼의 사람이 필요하다.
  • 여기서 생각이 든 부분은 1층이 건물의 시작이 아니겠구나라는 점이었다!
  • 규칙에 따르면, 1층의 거주자는 0층의 거주자들만큼의 사람이 필요하게 된다.
  • 따라서 건물의 진짜 시작은 0층이다.
  • k와 n에 1 <= k, n <= 14라는 조건이 걸려있던 점 역시 이 부분을 증명해준다!

• 입력 데이터의 최댓값은 14이기에, 재귀적인 풀이를 이용해보기로 했다.

  • 최대 재귀 깊이를 초과할 우려가 있지만, 14까지는 문제가 없을 것이라고 판단하였다.

풀이

def people_sum(k, n):
    if k == 0:                       # 0층인 경우
        for i in range(1, n + 1):
            apartment[k][i - 1] = i  # i - 1호에는 i의 값이 들어간다. 0층의 호수에는 1부터 n까지의 값이 차례대로 들어간다. 

    else:
        people_sum(k - 1, n)         # k가 0이 아닌 경우 계속 재귀호출을 한다. 
        cnt = 0                      # 매번 초기화해주어야 함
        for i in range(1, n + 1):
            cnt += apartment[k - 1][i - 1]  # (a - 1)층의 b호까지의 사람들을 전부 더한 값이 
            apartment[k][i - 1] = cnt       # a층의 b호에 필요한 사람의 수가 된다. 


for test_case in range(int(input())):
    k = int(input())                 # 아파트의 층 수
    n = int(input())                 # 대상이 되는 호수

    apartment = [[0] * n for _ in range(k + 1)]  # 0층이라는 존재가 있기 때문에 k + 1을 해주어야 한다. 
    people_sum(k, n)

    print(apartment[k][n - 1])       # n에서 1을 빼주어야 제대로 호수를 찾아갈 수 있다. 

읽어주셔서 감사합니다!