파이썬의 자료구조 - 조합 문제풀이

조합 문제풀이 (백준 온라인 저지 2775번)

조합 개념 정리 (DP 테이블)

• 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘
  

메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 기법

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식

조건

• 다이나믹 프로그래밍은 다음 조건들을 만족할 때 사용할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있고 그 작은 문제의 답을 모에서 큰 문제를 해결할 수 있는 경우

• 동일한 작은 문제를 반복적으로 해결해야하는 경우

78번 조합 설계

import sys
input = sys.stdin.readline
D = [[0 for j in range(15)] for i in range(15)]

for i in range(1,15) : # 리스트 초기화
    D[i][1] = 1 # i층의 1호는 항상 1의 값을 지니기 때문에 초기화할 수 있음
    D[0][i] = i # 0층의 i호는 i의 값을 지니도록 문제에서 주어짐

for i in range(1,15) :
    for j in range(2, 15) :
        D[i][j] = D[i][j-1] + D[i-1][j] # 일반화된 점화식

T = int(input()) # 테스트 케이스

for i in range(0, T) :
    K = int(input()) # 층수 입력
    N = int(input()) # 호수 입력
    print(D[K][N])