[백준] 1010-다리놓기

문제바로가기

결국 문제에서 요구하는 것은 mCn의 값이다. (조합구하기)
원래는 백트레킹 연습하던 게 생각나서 그걸로 코드를 완성했는데 당연하게도 메모리 초과가 났다.

#메모리 초과 (백트래킹 방법)
test = int(input())
count = 0
def back(start):
    global count
    if len(answer) == N:
        # print(" ".join(map(str, answer)))
        count+=1
        return
    for i in range(start, M+1):
        answer.append(i)
        back(i+1)
        answer.pop()
for _ in range(test):
    N, M = map(int, sys.stdin.readline().split())
    answer = []
    back(1)
    print(count)
    count = 0

백트레킹은 딱봐도 O(n^2)임. 뿐만아니라 리스트도 계속 생성/호출하고 메모리 초과가 날 것 같았다. 그래도 그냥 완성해보고 싶어서 해봤는데 일단 정답이 맞게 나오긴 한다.

import sys
sys.setrecursionlimit(10**6)

test = int(sys.stdin.readline())

def comb(n,m):
    result = 1
    
    for k in range(1, n+1):
        result *= m
        result /= k
        m-=1
    return int(result)

for _ in range(test):
    N, M = map(int, sys.stdin.readline().split())
    print(comb(N, M))

위가 최종코드
조합을 계산하는 수식을 보면 nCr일 때 n~(n-r+1)까지의 수를 곱한 값을 1~r까지 곱한수로 나눠준다. comb 함수를 만들어 간단하게 해결완료