[BOJ/백준 1010번][PYTHON] 다리놓기

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

뭐 풀까하다가 마지막으로 머리 식히는 겸 풀었다.

직관적인 그림 하나로 전부 설명이 가능한 문제다.

강을 기준으로 나뉜 두 빨간점을 연결하는 선을 그을 것이다. 그런데 절대로 교차하게 만들면 안된다.

 

단순히 경우의 수를 구하는 문제이다.

컴퓨터 프로그래밍을 해야겠다고 생각을 해보면, 재귀문제 같다. 어디를 선택하냐에 따라 경우의 수가 달라지고 결국 합치면 된다.

그렇게 생각해보면 재귀이기 때문에 Dynamic programming으로도 풀 수 있을 거라 생각이 든다. 어떠한 계산의 최적화라기 보단, 계산 자체의 양을 줄이는 용도의 표를 만들어 풀 수 있을 거라 생각한다. (이유라면, 시간 제한이 붙어있다 0.5초 였나? 뭔가 기분 나쁜 시간 제한)

근데 결론적으로는 공식을 사용하면 된다. 흔히 고등학교 때 확률과 통계 시간에 배웠던 조합 문제이다.

m이 강 동쪽의 많은 점이고, n이 서쪽의 점이다.

 

계산을 해보면 식은

이와 같다. 그러면 n자리에 m, r자리에 n을 넣으면 된다.

이것에 대한 이해는 조합에 대해서 생각을 해보면 된다.

 

구현은 아래와 같이 된다.

import sys
n = int(input())
count = 1
def fac(x):
    result = 1
    for i in range(x):
        result *= (i+1)
    return result
for i in range(n):
    a, b = map(int,sys.stdin.readline().split())
    c = fac(a)
    d = fac(b)   
    n_r = fac(b-a)
    re = d/(c*n_r)
    print(int(re))

변수 명은 간단한 문제이기 때문에 특별히 신경쓰지 않았다. 숫자가 커지면 0.5초에 걸릴 것 같다. for문으로 단순히 연산하는 것이기 때문에걸리는 시간이 그렇게 아름답지 않다.