다리놓기 [1010]

다리놓기 [1010]

백준 - https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

문제

• 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다.

• 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다.

• 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다.

  (N ≤ M)

• 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다.

  (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.)

• 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다.

• 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

---

입력

• 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.
• 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

• 각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

예시

 

---

풀이과정

• 처음의 방식은 재귀를 통해서 문제를 풀으려고 했다.
• 하지만 조합을 쓴다면 아주 간단한 문제였다.
• 강 건너편의 사이트들 중에서 만들수있는 다리 개수를 정하는 것으로 mCn 을 구현하면 된다.

 

 

---

• 기존 풀이과정
  • 재귀함수를 이용한다면 풀수있을 것이라고 생각한다.
  • 처음이 (3, 5) 상태라면 (2, 4) (2, 3) (2, 2) 를 호출할수 있도록 한다.
  • 그런데 코드는 논리상 맞다고 생각하는데 시간초과로 통과하질 못한다.
  • 13 29 입력시 한 7초를 기다려야하는데 확실히 오래걸리므로 그부분에서 잘못된것같다.

다리놓기 - recursive

---

느낀점

• 허무하다
• 컴퓨터 처럼 처리하려고 머리싸매고 재귀로 풀고있었는데 정작 답은 인간마냥 풀었다.
• 충분히 패턴을 고민하고 진행하는게 문제풀이에있어서 크다는걸 느낌