백준 - 2755. 부녀회장이 될테야(MJ)

📖#2755. 부녀회장이 될테야

백준 - 브론즈1

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

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

🔍Institution

“a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”

아파트는 0층부터 있고, 층마다 1호~n호까지 있다. 0층의 i호에는 i명이 산다.

floor(층) / ho(호)	0	1	…	n
0	0	1	…	n
1
…
k

🔍Approach

dp를 접근할 때에는 먼저 점화식을 세워야 한다. 점화식을 세우기 위해서는 나열을 하며 규칙을 발견해야 한다.

dp문제이므로, dp에는 각 층의 호마다 살고 있는 사람의 수를 저장한다. 이때 수는 누적이 되어야 한다. 따라서 이전 값을 활용한다.

먼저 0층일 때는, 호만큼의 사람 수가 있으므로 먼저 채워넣어준다. 이후 다른 층은 n호라면 1호부터 n호까지의 값을 더해야 한다. 더하면서 발견한 규칙은 아래와 같다.

• **i가 floor(층)이고, j가 ho(호)일 때,**
  • 0층인 경우 → dp[i][j] = j
  • 아닌 경우 → dp[i][j] = dp[i-1][j] + dp[i][j-1]

즉, 0층이 아닌 경우에는 아래 dp테이블에서처럼 대각선의 값을 더한다.

위의 방식을 사용하려면 dp의 크기를 [floor+1, ho+1]로 설정해야 한다.

이를 통해 아래와 같이 dp를 다시 정리할 수 있다.

floor(층) / ho(호)	0	1	2	3
0	0	1	2	3
1	0	1	3	6
2	0	1	4	10
3	0	1	5	15

🚩My submission

1. 테스트케이스 tc를 입력받는다.
2. tc만큼 반복하면서 floor(층)과 ho(호)를 입력받는다.
3. dp 리스트를 0으로 초기화한다. 인덱스에러가 나지 않도록 입력받은 floor와 ho보다 왼쪽, 위쪽으로 1씩 더 크도록 설정한다.
4. 첫 for문은 0부터 floor까지 반복하며, 안에 있는 for문은 1부터 ho만큼 반복한다. (ho는 1호부터 시작하므로)
   1. 만약 0층이라면, dp[i][j]의 값은 j의 값으로 넣어준다.
   2. 그게 아니라면, 위에서 세운 점화식을 넣는다. ( dp[i][j] = dp[i-1][j] + dp[i][j-1])
5. 입력받은 floor와 ho의 위치에 있는 dp값을 출력한다. (dp[floor][ho])

tc = int(input()) #testcase

for _ in range(tc):
    floor = int(input())
    ho = int(input())
    
    dp = [[0] * (ho + 1) for i in range(floor + 1)]
    
    for i in range(floor+1):
        for j in range(1, ho+1):

            if i==0:
                dp[i][j] = j
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    print(dp[floor][ho])

🚩Others submission

출처: **백준 2775번 [파이썬 알고리즘] 부녀회장이 될테야**

t = int(input())

for _ in range(t):  
    floor = int(input())  # 층
    num = int(input())  # 호
    f0 = [x for x in range(1, num+1)]  # 0층 리스트
    for k in range(floor):  # 층 수 만큼 반복
        for i in range(1, num):  # 1 ~ n-1까지 (인덱스로 사용)
            f0[i] += f0[i-1]  # 층별 각 호실의 사람 수를 변경
    print(f0[-1])  # 가장 마지막 수 출력

• 내가 짠 코드보다 훨씬 간단하다.
• 0층의 값을 굳이 if문으로 주지 않고도 코드를 구현할 수 있다는 것을 알게 되었다.

💡TIL

• 이번에 기억 남은 건 [프로그래머스-등굣길] 문제였는데, 그 문제는 최단경로로, 고등학교 수학시간에 배웠던 풀이를 이용했다. 그걸 기억하고 [백준- 부녀회장이 될테야] 문제를 풀었는데 그 개념을 활용하니까 쉽게 풀렸다! 기록해놓길 잘했다.
• dp문제 풀이는
  • 나열 후 규칙 찾기 → 규칙을 토대로 점화식 세우기 → 예외가 없는지 검토 후 코드 작성하기
  • 이게 베스트인 것 같다.