[실버 4] 2407번: 조합

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

2407번: 조합

---

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

---

사고의 흐름

• m, n의 상한이 100인데 재귀로 풀 수 있을까? Python으로는 힘들어 보이는데. 일단 해보고 안 되면 Pypy로 제출해보고, 그래도 안 되면 C++로 짜든지 다른 방법을 쓰든지 하자.
• 역시 시간 초과가 뜨네. 다른 방법을 쓰자. DP 쓰면 되겠네.

내가 작성한 소스코드

# 시간 초과

import sys
input = sys.stdin.readline


def get_combination(x, n, r, li, depth):
    global cnt
    
    if len(li) == r:
        cnt += 1
        return
    
    if depth == n:
        return

    li.append(sample[x])
    get_combination(x+1, n, r, li, depth+1)
    del li[-1]
    get_combination(x+1, n, r, li, depth+1)


n, m = map(int, input().split())
sample = [i for i in range(n)]
global cnt
cnt = 0

get_combination(0, n, m, [], 0)
print(cnt)

import sys
input = sys.stdin.readline


def get_combination(n, r, dp):
    if n == r or r == 0:
        return 1

    if dp[n][r] != -1:
        return dp[n][r]
    
    dp[n][r] = get_combination(n-1, r, dp) + get_combination(n-1, r-1, dp)
    return dp[n][r]


n, m = map(int, input().split())
dp = [[-1] * (m+1) for _ in range(n+1)]

print(get_combination(n, m, dp))

피드백

• 최대한 다른 사람의 코드를 보면서 문제 푸는 시간을 단축시키자. 설령 그대로 따라 치는 한이 있더라도 다른 코드를 보면서 사고의 지평을 넓혀야 한다.

여담

 백준 6603번 문제를 재귀 함수로 푸는 방법이 이해가 안 되서 풀어보았다. 이전에 작성한 코드를 참고하면서 재귀로도 풀긴 했는데 아직도 잘 모르겠다. 정말 재귀 함수는 이해가 될 것 같다가도 다시 모르겠다….