[백준 2775] 부녀회장이 될테야

문제

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

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

 

입력

첫째 줄에 테스트 케이스가 입력된다.

테스트 케이스마다 한 줄에 하나씩 K와 N을 입력한다.

K와 N은 1이상 14이하이다.

 

출력

K층 N호에 몇 명이 사는지 출력한다.

---

접근

처음에 문제가 잘 이해되지 않았다.

그래서 그림을 그려보면서 이해를 하였다. 그네 마지막 줄에 0층의 i호에 i명이 산다는 것을 보지 않았다. (문제를 꼼꼼히 읽는 습관이 아직도 길들여지지 않았다.)

그래서 먼저 0층의 3호까지 있다면 1호부터 3호까지 1 2 3 명이 산다.

그리고 1층의 1호부터 3호까지는 1, (1+2), (1+2+3)이 살게된다

 

여기서 규칙을 발견하였는데 모든 층의 1호는 무조건 1명이다. 그리고 해당 층의 n호는 같은 층의 n-1호와 아래층의 n호를 더하면 k층의 n호에 몇 명이 사는지 알 수 있었다.

 

구현

K층 N호를 입력하고

층은 K+1만큼 생성하고 호는 N만큼 생성하도록 한다.

    K = int(input())
    N = int(input())
    matrix = [[0 for _ in range(N)] for _ in range(K+1)]

 

그리고 먼저 0층의 N호까지 각각 몇 명이 사는지 구한다.

    for n in range(N):
        matrix[0][n] = n+1

 

이제 1층부터 K층까지 순서대로 구한다.

y층의 x호는 y-1층의 x호와 y층의 x-1호의 사람 수를 더한 값이다.

만약 x가 0호라면 1을 넣어주도록 한다.

    for y in range(1, K+1):
        for x in range(N):
            if x == 0:
                matrix[y][x] = 1
            else:
                matrix[y][x] = matrix[y-1][x] + matrix[y][x-1]

 

그리고 K층의 N-1을 출력하도록 한다.

answer = matrix[K][N-1]

---

전체 코드

test_case = int(input())
for _ in range(test_case):
    # K층 N호
    K = int(input())
    N = int(input())
    matrix = [[0 for _ in range(N)] for _ in range(K+1)]

    for n in range(N):
        matrix[0][n] = n+1
    answer = 0
    for y in range(1, K+1):
        for x in range(N):
            if x == 0:
                matrix[y][x] = 1
            else:
                matrix[y][x] = matrix[y-1][x] + matrix[y][x-1]

    answer = matrix[K][N-1]
    print(answer)