[백준 2775번] 부녀회장이 될테야 파이썬 풀이

부녀회장이 될테야

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	79625	44615	38149	56.523%

 

문제

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

이 아파트에 거주를 하려면 조건이 있는데, “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

브론즈 1의 난이도 치고 꽤나 고전했던 문제이다.

동적 계획법(다이나믹 프로그래밍)을 이용하여 해당 문제를 풀 수 있으며, 풀이는 다음과 같다.

 

우선 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 라는 조건에 주목해야 한다.

예를 들어 203호에 사는 사람은 101호의 거주인 수 + 102호의 거주인 수 + 103호의 거주인 수 를 합한만큼의 인원이 살아야 한다는 의미이다.

또한 0층의 경우 00n호 에는 n명이 산다는 조건이 있으므로 이를 이용하여 dp테이블에 값을 기록하는 메모이제이션 기법을 이용하여 상위 층에서 하위 층의 인원수를 재계산하는 일이 없도록 하여야 시간복잡도 문제 없이 문제를 해결할 수 있다.

 

예를 들어 203호에 사는 사람의 수를 계산한다고 가정해보자.

k층 n호에 사는 사람의 수를 f(k,n)이라고 할때 f(k,n)은 문제의 조건에 따라 다음 식으로 표현할 수 있다.

 

f(k,n) = f(k-1,1) + f(k-1,2) + ... + f(k-1,n)

 

이를 통해 203호의 경우를 계산해보면

203 = 101 + 102 + 103과 같고.

101,102,103호 또한 아직 0층이 아니므로 각각 001, 001+002, 001+002+003 으로 식이 표현될 것이다.

 

k와 n의 값이 적은경우 반복문을 통해 처음부터 계산을 진행한다면 시간복잡도의 문제가 없을 것이나, k와 n의 값이 커지면 커질수록 중복되는 계산의 크기가 커질것이기 때문에, 시간복잡도 문제가 발생하게 될것이다.

 

이를 해결하기 위한 방안으로 각 호실의 사람들이 몇명이 사는지를 계산과 동시에 배열에 미리 기록을 해둔다면 중복되는 계산 없이 시간을 단축 할 수 있다.

해당 아이디어를 갖고 다음 코드를 살펴보자.

# 테스트 케이스의 개수
t = int(input()) # 계산을 몇번 수행할 것인지

# 14x14까지 가능하므로 101호의 경우 dp[1][1]
dp = [[0]*15 for i in range(15)]

# t번 수행
for i in range(t):
    # k층
    k = int(input())
    # n홀
    n = int(input())

    for j in range(k+1):
        for h in range(n+1):
            if j == 0:  # 0층의 경우만 알고있음
                dp[j][h] = h  # n호의 경우 n명이 거주함을 기록
            else:  # 0층이 아닌경우
                if dp[j][h] == 0:  # 현재 해당층과 관련하여 dp테이블에 정보가 없다면
                    for l in range(h+1):
                        dp[j][h] += dp[j-1][l]
                else:  # 값이 기록되어 있는경우
                    continue  # 다음으로 넘어간다.
    print(dp[k][n])

 

배열에 계산 결과를 기록해두는 메모이제이션 기법을 이용하기 위해선 기본적으로 배열이 필요하다.

문제의 조건에 따라 k와 n은 14를 넘을 수 없으므로 최대로 가능한 호실은 1414호임을 알 수 있다.

해당 층의 호실까지 기록하기 위해 2차원 배열 dp[15][15]를 작성하여, 000호부터 1414호실에 대한 정보를 저장할 수 있도록 한다.

for j in range(k+1):
    for h in range(n+1):

 

위의 2중 반복문을 통해 0층부터 k층까지, 그리고 각각의 층에서 0호실부터, n호실까지 인원수 계산을 시작한다.

우리가 알고 있는 정보는 0층의 n호실에 대한 정보이므로 만약 j가 0층이라면 해당 호실에 대한 정보를 기록하도록 하고,

0층이 아닌경우에는 f(k,n) = f(k-1,1) + f(k-1,2) + ... + f(k-1,n) 공식을 수행하기 위해 다시 반복문을 돌면서 dp테이블에서 값을 찾아 해당층의 주민 수가 몇명이 될지를 계산하고 다시 활용하기 위해 dp테이블에 기록한다.

또한 바깥의 이중 반복문을 수행하며 dp테이블에 이미 기록된 호실을 재계산하지 않도록 하기 위해 dp테이블의 값이 0이 아니라면(즉, 이미 기록되어 있다면) continue를 통해 다음 수 부터 반복을 진행하도록 한다.

if j == 0:  # 0층의 경우만 알고있음
    dp[j][h] = h  # n호의 경우 n명이 거주함을 기록
else:  # 0층이 아닌경우
    if dp[j][h] == 0:  # 현재 해당층과 관련하여 dp테이블에 정보가 없다면
        for l in range(h+1):
            dp[j][h] += dp[j-1][l]
    else:  # 값이 기록되어 있는경우
        continue  # 다음으로 넘어간다.

 

이를 이용하면 동적 계획법을 이용하여 문제를 풀 수 있다.

 

더 깔끔한 풀이 방법이 아마 존재할것이라고 생각하나, 동적계획법을 활용한 문제에 아직 익숙하지 않아 다소 복잡하게 문제를 풀게 되었다.

더 다양한 문제를 풀어 더 깔끔한 방법을 생각할 수 있도록 노력해야겠다.

 

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

2775번: 부녀회장이 될테야