백준 BaekJoon Online Judge // 2775

백준 알고리즘 BaekJoon Online Judge 2775번 "부녀회장이 될테야" 문제입니다.

TC = int(input())
for i in range(0, TC):
  K = int(input())
  N = int(input())
  lst = [list(range(1, N+1))]
  for j in range(1, K+1):
    temp = []
    for l in range(0, N):
      temp.append(sum(lst[j-1][0:l+1]))
    lst.append(temp)
  print(lst[K][N-1])

문제의 내용은 아래와 같다.

 

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

 

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

 

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

 

일단 처음에는 0층에 어떻게 살고있는지를 파악해야한다.

 

0층 i호에는 i명이 산다는 말은 0층 1호에는 1명, 0층 2호에는 2명, 0층 3호에는 3명... 이렇게 이어진다.

 

이를 리스트화 시키면 0층에 살고 있는 각 호당 사람의 수는 [1, 2, 3, 4, ...., N-1, N] 이렇게 된다.

 

여기서 내가 리스트의 크기를 N으로 단정지은 이유는 N보다 클 필요가 없기 때문이다.

 

N은 최대 14라고 되어있지만 14까지 만들 필요가 없고 더 작게 만들 수 있으면 작게 만드는 것이 최선이다.

 

다음 1층은 0층의 주민 수를 참고한다.

 

1층 1호에는 0층 1호까지의 사람 수 만큼을 필요로 하므로 리스트 0층에서[0:1]까지의 합을 구하면 된다.

 

1층 2호에는 0층 1호부터 0층 2호까지의 사람 수 만큼을 필요로 하므로 리스트 0층에서[0:2]까지의 합을 구하면 된다.

 

이러한 방식으로 1층을 채우고 다음 층은 이전 층의 주민 수를 참고하면 된다.

 

이런 식으로 참고를 하면 층마다 주민 수가 담겨져 있는 이중 리스트를 생성하게 된다.

 

층도 마찬가지로 최대 14까지로 되어있지만 작게 만드는 것이 최선이므로 입력된 층에 맞게까지만 만든다.

 

이중 리스트를 완성시켰으면 이제 이중 리스트의 [K][N-1] 인덱스 값을 참조하면 된다.

 

층은 0부터 시작하기 때문에 K로 참조하면 되고 호 수는 1부터 시작이기 때문에 N이 아니라 N-1로 참조해야 한다.