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

부녀회장이 될테야 - 2775

문제 링크

2775번: 부녀회장이 될테야

성능 요약

메모리: 31256 KB, 시간: 64 ms

분류

다이나믹 프로그래밍, 구현, 수학

문제 설명

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

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

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

입력

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

출력

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

---

🙋 문제 해석

일단 이 문제는 부녀회장과는 상관이 없고, 아파트 거주조건만 확인하면 됩니다.

 

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

예를들어 0층의 10호까지는 [0,1,2,3,4,5,6,7,8,9,10]
1층의 10호까지는 [0,1,3,6,10,15,...]
2층의 10호까지는 [0,1,4,10,20...]

 

규칙을 보면 층 별 사람이 계속 많아지는 걸 확인 할 수 있습니다. 보면 피보나치수열처럼 규칙성이 나열되어 있는 것을 확인 할 수 있습니다.

 

 

 

이러한 규칙들은 다이나믹프로그래밍을 활용하면 쉽게 풀 수 있습니다.저는 bottom-up 방식으로 해결하였습니다.

한 번으로 코딩 역량을 향상하는 동적프로그래밍 기법을 알아보자! 🔥

 

 

[[0, 1, 2, 3, 4],
 [0, 1, 3, 6, 10],
 [0, 1, 0, 0, 0],
 [0, 1, 0, 0, 0],
 [0, 1, 0, 0, 0]]

이런식으로 아파트 구조도가 있다고한다면, 여기서 규칙성을 발견하면 됩니다.

 

 

dp[1][2] 을 구하고자 한다면

dp[0][2] + dp[1][1] 이러한 점화식을 코드로 나타내면됩니다.

 

---

🔑 Solution 🔑

for _ in range(int(input())):
    # 층 수와 호수 입력
    floor=int(input())
    hosu=int(input())
    # dp 리스트 초기화
    dp = [[0]*(hosu+1) for i in range(floor+1)]
    # 0층(i=0)에서 각 호실(j)에 사는 사람 수 초기화
    for i in range(hosu+1):
        dp[0][i] = i
    # i층에서 1호실에 사는 사람 수 초기화
    for i in range(floor+1):
        dp[i][1] = 1
    # 점화식에 따라 dp 리스트 채우기
    for i in range(1,floor+1):
        for j in range(2,hosu+1):
            dp[i][j] = dp[i-1][j]+dp[i][j-1]
    print(dp[floor][hosu])

다이나믹 프로그래밍의 점화식을 이용하여 dp 리스트를 채웁니다. 이때, dp[i][j]는 dp[i-1][j]과 dp[i][j-1]을 이용하여 계산됩니다. 따라서, dp[0][i]와 dp[i][1]은 초기화해주어야 합니다.

최종적으로, dp 리스트에 저장된 값 중 dp[floor][hosu]가 원하는 결과입니다. 

이 값은 각 방에 사는 사람의 수를 계산하여 저장한 값 중 마지막 값입니다. 

---

🕐 시간 복잡도

O(floor * hosu)

dp 리스트의 각 요소를 계산하는데 O(1)의 시간이 소요되므로, dp 리스트를 채우는 데 걸리는 시간은 O(floor * hosu) 입니다. 또한, 입력을 받는 부분은 O(1)의 시간이 소요되므로, 전체 코드의 시간 복잡도는 O(floor * hosu) 입니다. 

---

🙇