[백준] 2775번 부녀회장이 될테야 파이썬 정답 코드

2775번: 부녀회장이 될테야

---

1. 문제 내용

 

 

2. 접근 방식

• 다이나믹 프로그래밍(DP)

a층의 b호에 살려면 a-1층의 1호부터 b호까지의 사람 수 합만큼 데려야 살아야 한다. 예를 들면, 2층 3호에 사는 사람 수는 1층 1호 + 1층 2호 + 1층 3호 = 0층 1호 + ( 0층 1호 + 0층 2호) + ( 0층 1호 + 0층 2호 + 0층 3호)이다.

즉, ① 2층 3호라는 큰 문제를 작은 문제로 나눌 수 있으며 ② 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다. (이것이 취업을 위한 코딩 테스트이다, p.212) 따라서 이 문제는 dp이다.

 

• dp를 2차원 리스트로 설정한다.

층과 호수라는 2개의 값이 있기 때문이다. 사실 처음엔 1차원 리스트로 설정했었지만, 인덱스를 계산하기가 복잡하여 2차원 리스트로 수정하였다.

 

 

3. 정답 코드

t = int(input())

# 입력
data = []
for _ in range(t):
    k = int(input())
    n = int(input())

    data.append((k, n))

# 실제 로직 시작
for tu in data:
    k, n = tu[0], tu[1]

    dp = [[0] * (n + 1) for _ in range(k + 1)]

    # 0층
    for i in range(1, n + 1):
        dp[0][i] = i

    for i in range(1, k + 1):
        for j in range(1, n + 1):
            if not dp[i][j]:
                for l in range(1, j + 1):
                    dp[i][j] += dp[i - 1][l]

    print(dp[k][n])