허비의 기술블로그

강이 위에서 아래로 흐르고 서쪽, 동쪽 땅으로 구분돼있다. 서쪽과 동쪽에는 각각 다리를 놓을 수 있는 포인트들이 N, M개 있다. (M >= N) 이때 서쪽에서 동쪽으로 다리를 놓으려고 할 때 다리를 놓을 수 있는 최대 경우의 수를 찾는 문제다. 시간 복잡도: O(MN) 풀이과정 강의 서쪽 땅 N개의 포인트에서 동쪽 땅 M개의 포인트를 연결하고자 하며, N은 M보다 작거나 같다. 이때 강의 동쪽에 연결할 M개의 포인트 중에 N개를 선택하면 서쪽에서 이어질 다리가 교차하면 안 되므로 다리를 짓는 경우가 1개 나온다. 즉 M개의 포인트에서 N개를 선택하는 경우의 수가 이 문제의 정답이다. 주의할점 조합은 수가 커질수록 결괏값이 커지므로 수의 범위를 조심해야 한다. 문제에서는 M, N의 최댓값이 30이기 때문..