[백준 알고리즘] 조합(2407)

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

이 문제는 메모이제이션이라는 방법을 이용하여 조합의 공식에 따라 구해보겠습니다.

조합

$$_{n}C_{r}=_{n-1}C_{r-1}+_{n-1}C_{r}$$

여기 파스칼의 삼각형이라 불리는 형태가 있습니다.

$$_{4}C_{2}=_{3}C_{1}+_{3}C_{2}$$

위와 같은 예시를 통해 원하는 값을 좌우측 상단을 더하면 일치한다는 것을 알 수 있습니다.

이 과정이 계속 반복되면 결국 0C0 1C0 1C1의 합으로 모든 조합을 표현할 수 있다는 것을 알 수 있습니다.

메모이제이션

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다.

(출처: 나무위키)

메모이제이션을 이용하면 조합의 값을 구하기 위해 파스칼의 삼각형 꼭대기까지 올라갈 필요 없이 바로 좌우측 상단의 값을 메모리에서 불러와 이용할 수 있습니다.

파이썬 코드로 구현해보겠습니다.

 

fact = [[0 for i in range(101)] for j in range(101)]
fact[0][0] = fact[1][0] = fact[1][1] = 1
for i in range(2, 101):
    for j in range(0, i+1):
        if i == j or j == 0:
            fact[i][j] = 1
        elif fact[i][j] == 0:
            fact[i][j] = fact[i-1][j-1] + fact[i-1][j]

N, K = map(int, input().split())
print(fact[N][K])

먼저 입력값의 최대값이 100이므로 인덱스 100까지의 리스트를 만들어 둡니다.

그리고 조합의 공식에 따라 이용하게 될 0C0 1C0 1C1의 값을 각각 1으로 초기화합니다.

그리고 반복문을 통해 각 인덱스에 맞는 조합의 값을 리스트에 저장합니다.

그리고 입력 값에 따라 리스트의 값을 불러와 출력하면 이 문제를 간단히 해결할 수 있습니다.