[DP] 2775번 부녀회장이 될테야 - 브론즈1

[heerucan]

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

t = int(input())

for _ in range(t):
    k = int(input()) #몇 층
    n = int(input()) #몇 호

    D = [[0] * 15]*15

    # 0층의 값을 먼저 구해야 되지! 0층에는 1호~14호까지 존재함
    # D[0][1] = 1
    # D[0][2] = 2
    # D[0][3] = 3
    # D[0][4] = 4
    # D[0][5] = 5
    # D[0][6] = 6
    # D[0][7] = 7
    # D[0][8] = 8
    # D[0][9] = 9
    # D[0][10] = 10
    # D[0][11] = 11
    # D[0][12] = 12
    # D[0][13] = 13
    # D[0][14] = 14

    # 0층 1~14호까지 사람 수를 먼저 넣어줘야 함
    for i in range(1, 15):
        D[0][i] = i

    for i in range(1, k+1):
        for j in range(1, n+1):
            D[i][j] = D[i][j-1] + D[i-1][j]

    print(D[k][n])

생각 문풀

후,, 이 문제는 브론즈1이라고 만만하게 봤다가 점화식을 알듯말듯 모르겠어서 팡시기한테 어떻게 접근해야 하는지 물어봤더니
0층부터 2층까지만 손으로 써보라고 했다.
그랬더니 점화식이 바로 보이는 것;;;

   # 1 4 10 20 ? ? ? ? ? ? ? ?
   # 1 3 6  10 15 21 28 36 45 55 66 78 91 105
   # 1 2 3  4  5  6  7  8  9  10 11 12 13 14

• 우선 2차원 배열을 써야 하는 건 머리를 굴렸더니 바로 알 수 있었다.
  (실은 이거 알아내서 다행이라고 생각했다. 이것도 몰랐으면 빠가사리라고 울엇을 것임.........༼ ༎ຶ ෴ ༎ຶ༽
  왜냐면 어제 울엇거든.. 진짜 못풀어서 울엇어..ㅠ)

• D[k][n] = k층 n호에 사는 사람의 수

• 점화식은 어떻게 구하냐?
  1층의 4호 = 1층의 3호 사는 사람 + 0층의 4호
  D[k][n] = D[k][n-1] + D[k-1][n]