📃문제
평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.
이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.
아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.
📃입력
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
📃출력
각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.
제한
1 ≤ k, n ≤ 14
📃예제 입력 1
2
1
3
2
3
📃예제 출력 1
6
10
✏️문제 탐색하기
특정 규칙에 따라 아파트의 각 층과 호에 사는 사람의 수를 계산하는 문제이고 주어진 층(k)과 호(n)에 몇 명이 사는지를 구하기.
주어진 조건:
- 아파트는 0층부터 시작하며, 각 층에는 1호부터 n호까지 존재합니다.
- 0층의 i호에는 i명이 살고 있습니다. 예를 들어, 0층 3호에는 3명이 살고, 0층 5호에는 5명이 삽니다.
- a층 b호에 사는 사람 수는 (a-1)층의 1호부터 b호까지의 사람 수의 합입니다.
예를 들어 1층 3호에 사는 사람 수는 0층 1호 + 0층 2호 + 0층 3호의 사람 수의 합입니다. <- 이게 핵심
✏️알고리즘 선택
동적 프로그래밍을 사용하여 풀 수 있습니다. 각 층과 호에 사는 사람의 수는 아래층에 있는 사람 수를 기반으로 계산되므로 이전 계산 결과를 활용하여 다음 값을 구할 수 있습니다.
최대 14층 각 층에 최대 14호까지 필요한 값을 미리 계산합니다.
배열을 채우는 데 필요한 시간 복잡도는 O(15 x 15) = O(225)입니다.
✏️코드 설계하기
- 테스트 케이스 수 T를 입력받습니다.
- k와 n 값을 각 테스트 케이스마다 입력받습니다.
- arr[a][b]를 사용하여 각 층과 호의 사람 수를 저장합니다.
- 먼저 0층의 각 호에 대해 arr[0][i] = i + 1로 초기화합니다.
- 나머지 층은 arr[a][b] = arr[a][b-1] + arr[a-1][b] 이런식으로 사람 수를 계산해 채워넣습니다.
- 미리 계산된 arr 배열을 이용해 각 테스트 케이스에 대해 arr[k][n-1]을 출력합니다.
✏️시도 회차 수정 사항
1회차
이번 문제는 문제 부터 이해하기 쉽지 않아서,, 문제만 몇 번을 읽은지 기억이 안 날정도,,
처음엔 0층 부터 14층까지, 1호 부터 14호까지를 이해하고
arr = [[0] * 15] * 152차원 배열을 이런 식으로 만들려고 했다가 모든 행이 동일한 리스트를 참조하게 되어서 하나의 행을 수정하면 다른 행도 같이 수정되는 문제가 발생됐다...
이것이 얕은 복사라고 한다
그래서 알아 본 결과 내가 원하는 답은 깊은 복사해 해결하는 것.
깊은 복사는 원본 객체와 그 하위 객체들까지 모두 새롭게 복사하여 완전히 독립적인 객체를 만드는 것이라고 한다.
그래서 리스트 컴프리헨션으로 작성 완료!
arr = [[0] * 15 for _ in range(15)]✏️코드 구현
import sys
T = int(sys.stdin.readline())
arr = [[0] * 15 for _ in range(15)]
for i in range(15):
arr[0][i] = i+1
for a in range(1, 15):
for b in range(15):
arr[a][b] = arr[a][b-1] + arr[a-1][b]
for _ in range(T):
k = int(sys.stdin.readline())
n = int(sys.stdin.readline())
print(arr[k][n-1])
