백준 1010번 문제(다리 놓기) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

정답 코드는 아래와 같습니다.

def facto(x):
  if x == 0 or x == 1:
    return 1
  else:
    return x * facto(x-1)
 
def comb(n, r):
  return int(facto(n) / (facto(r) * facto(n-r)))
 
def solve():
  a, b = [int(x) for x in input().split()]
  print(comb(b, a))
 
t = int(input())
for _ in range(t):
  solve()
 

 

이 문제는 고등학교 수학에서 배우는 조합을 활용한 문제입니다.

서쪽 지점의 수가 동쪽 지점의 수보다 작으며, 서쪽 지점에서는 동쪽으로 모두 연결된다고 했으니,

"동쪽 지점에서 서쪽 지점과 연결할 위치를 선택할 수 있는 경우의 수" 가 결국은 "연결 가능한 경우의 수" 가 됩니다.

왜냐하면, 다리가 서로 겹치지 않아야 하기 때문에 동쪽에서 점들이 선택이 된 순간 서쪽의 어떤 지점들과 연결이 될지 결정되기 때문입니다.

즉, nCr 인 것이죠. 이 문제에서 주어진 문자를 그대로 쓰자면 mCn 이라고 할 수 있겠네요.

 

728x90

 

이 문제의 핵심은 주어진 문제가 결국 조합 문제와 동일한 문제라는 것을 알아내는데 있습니다.

이것을 알아낸 순간 그 다음은 단순하게 정해진 식을 코드로 옮기면 될 뿐입니다.

 

순열, 조합, 확률 등을 활용하는 문제가 코딩테스트에 빈번하게 등장하지는 않습니다. 하지만 분명히 등장하기는 합니다.

따라서 해당 내용들에 대해서 숙지하고, 간단한 기본 예제들에 대해서 풀어보는 정도의 학습은 필요하다고 생각합니다.

 

풀이는 아래 영상 참고 바랍니다.

www.youtube.com/watch?v=TSwkzl7DxMk

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)