백준 2775번 - 부녀회장이 될테야 (Python3 풀이)

문제

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

 

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

 

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

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

예제 입출력

입력

2
1
3
2
3

출력

6
10

 

Python3 문제풀이

수열의 합 공식을 세워서 문제를 풀어도 되겠지만, 그렇게 풀지 않고 그냥 말 그대로 문제를 풀었습니다.

 

테스트 케이스로 여러번 수행하는 것을 보고, 메모이제이션(Memoization)을 이용하는것이 좋겠다고 생각했습니다.

• 메모이제이션을 이용해서 몇호에 몇명이 살고 있는지 이미 계산된 곳은 다시 계산하지 않는다

즉, 제가 생각하는 포인트는 4가지 입니다.

1. 메모이제이션을 이용한다.
2. 0층의 i호에는 i명이 살고 있다.
3. 1호는 무조건 1명이 살고 있다.
4. r층의 c호에 사는 사람을 f(r, c)라 했을때, f(r,c) = f(r-1, 1) + f(r-1, 2) + ... + f(r-1, c) 이다.

import sys


def _input():
    return int(sys.stdin.readline().strip())


def solve(memo, r, c):
    # 이미 계산한 적이 있는 경우
    key_name = "r{}c{}".format(r, c)
    if memo.get(key_name, None) is not None:
        return memo[key_name]

    if r <= 0:
        # 0층
        memo[key_name] = c

    else:
        # 0층이 아닌 경우

        if c == 1:
            # 각 층의 첫번째는 1
            memo[key_name] = 1

        else:
            # 나머지 경우
            memo[key_name] = 0
            for _ in range(1, c+1):
                memo[key_name] += solve(memo, r-1, _)

    return memo[key_name]


if __name__ == "__main__":
    t = _input()
    _memo = dict()  # memoization

    for _ in range(t):
        print(solve(_memo, _input(), _input()))

메모이제이션(memoization)을 이용할 때 보통 배열을 이용하여 표현하지만,

저는 딕셔너리(Dictionary)를 이용하여 표현해봤습니다.

 

위와같이 딕셔너리를 이용한 이유는 배열을 사용하게되면 필요하지 않은 공간도 사용해야합니다. (아래 그림 참조)

이해를 돕기 위한 그림

그래봐야 많이 차이는 안나지만, 숫자가 커질수록 사용하는 공간은 많아집니다.

 

그리고 가독성을 높이기 위해 키값을 row의 r, column의 c를 따서 r층수c호수 와 같이표현했습니다.

r1c2: 1층의 2호
r3c4: 3층의 4호
r100c100: 100층의 100호

풀이 결과

문제 풀이 결과

본 글은 직접 문제를 풀어보고 작성한 글입니다. 
더 좋은 방법이 있거나 틀린부분이 있다면 댓글로 공유해주세요!

원본 링크

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

2775번: 부녀회장이 될테야