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

---

소스코드

N = int(input())

for _ in range (N):

  k = int(input())

  n = int(input())

  dp = [[i+1 for i in range (n+1)] for j in range(k+1)]

  for floor in range (1,k+1):

    for ho in range (1,n+1):

      dp[floor][ho] = dp[floor-1][ho] + dp[floor][ho-1]

  print(dp[k][n-1])

---

알고리즘

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 

[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120], 

[1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680], 

[1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060], 

[1, 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, 6188, 8568, 11628], 

[1, 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, 18564, 27132, 38760], 

[1, 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, 31824, 50388, 77520, 116280], 

[1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 43758, 75582, 125970, 203490, 319770], 

[1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92378, 167960, 293930, 497420, 817190], 

[1, 11, 66, 286, 1001, 3003, 8008, 19448, 43758, 92378, 184756, 352716, 646646, 1144066, 1961256], 

[1, 12, 78, 364, 1365, 4368, 12376, 31824, 75582, 167960, 352716, 705432, 1352078, 2496144, 4457400], 

[1, 13, 91, 455, 1820, 6188, 18564, 50388, 125970, 293930, 646646, 1352078, 2704156, 5200300, 9657700], 

[1, 14, 105, 560, 2380, 8568, 27132, 77520, 203490, 497420, 1144066, 2496144, 5200300, 10400600, 20058300], 

[1, 15, 120, 680, 3060, 11628, 38760, 116280, 319770, 817190, 1961256, 4457400, 9657700, 20058300, 40116600], 

[1, 16, 136, 816, 3876, 15504, 54264, 170544, 490314, 1307504, 3268760, 7726160, 17383860, 37442160, 77558760]

 

dp문제다. 자신의 밑의 층 중 호수 가 낮은 숫자를 더한 값을 갱신해 나가면 된다.

예를 들어

2층 3호면

1층 3호에 있는 사람들을 전부 더한 값이 와야한다.

그러면 1 + 3 + 6 = 10