[백준 / #1010 / C++] 다리놓기

전부터 올려야지 올려야지 하다가 이제서야 올리게 된 알고리즘이다.

 

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

1010번: 다리 놓기

 

문제에서 제공된 조건은 우선 0 < N < M <= 30 이고 첫째줄에 테스트 케이스의 개수 T가 주어지면 T의 개수 만큼 N과 M의 쌍이 주어지고 각각의 한 쌍의 가능한 경우의 수를 구하는 문제이다.

 

이제 문제를 이해해 보자면 우선 강의 서쪽에는 N개의 사이트가, 강의 동쪽에는 M개의 사이트가 존재한다.

 

강의 서쪽 사이트 개수인 N개가 강이 동쪽 사이트 개수인 M개보다 무조건 적고 (문제의 조건에 의해), 다리는 교차해서 놓을 수 없다. 고등학교 수학 시간에 많이 본 듯한 문제이다.

 

그렇다 바로 조합(combination) 문제이다.

 

이 문제가 조합과 관련된 문제인 이유는 우선 강의 서쪽 사이트 N은 모두 선택될 수 밖에 없고, M은 M > N 이기 때문에 강의 동쪽 사이트는 몇개 남을 수 밖에 없다. 

 

강의 서쪽 ) ( 강 ) ( 강의 동쪽

그림을 보면서 설명하자.

 

위에서 강의 동쪽에 빨간 체크 된 사이트에 다리를 놓는다고 하자.

다리는 교차 될 수 없으므로 강의 동쪽에 존재하는 사이트가 다리로 연결 될 수 있는 사이트는 순서와 상관 없이 무조건 서쪽에 한 사이트와 연결 될 수 밖에 없다.

 

따라서 동쪽의 사이트의 총 개수에서 서쪽의 사이트 개수 만큼 순서에 상관 없이 고르는 것과 같으므로 조합을 사용하면 된다.

 

그럼 이제 코드를 살펴보자.

 

밑에 코드는 시간초과가 난 코드이다.

시간 초과가 나는 코드이다.

재귀함수를 통해 조합을 계산하는 코드를 만들었고 자신있게 제출하였으나 시간초과가 나고 말았다.

조금 더 빠른 시간 계산을 위해 nCr에서 r = 1 일 경우와 r = n - 1 일 경우도 조건에 추가해줬으나 시간초과가 나고 말았다.

 

그래서 고민을 해 본 결과 이렇게 재귀함수로 복잡하게 짤 필요가 없었다.

 

어차피 M <= 30 이고 제한 시간이 0.5초 이므로 30까지의 모든 조합의 수를 계산해주고 꺼내다 써도 충분한 시간이었다.

 

따라서 모든 조합을 계산해주었고 이 과정에서 동적계획법(dynamic programming)을 사용했다.

코드는 이와 같다.

 

미처 설명하지 못한 부분이 있는데 재귀함수로 구현한 조합도, 동적계획법을 이용한 조합도 모두 조합의 성질을 이용한 것이다.

조합의 성질을 이용하여 조합 계산을 간단히 하기 위해 n = 2부터 n = 1에 저장되어있는 값을 이용해 차근차근 계산해나가면 빠르고, 정확하게 값을 구해낼 수 있다.

 

이렇게 모든 값을 계산하고 입력되는 n과 m의 값에 해당하는 mCn 의 값을 찾아서 사용하면된다.