백준 1010번(다리 놓기) 파이썬(python)으로 해결

백준 1010번은 경우의 수를 구하는 방법입니다.

이는 수학의 힘을 빌려 공식을 쉽게 알아낼 수 있었습니다.

 

 

조건

 

서쪽(N)과 동쪽(M)의 사이트 개수가 같으면 경우의 수가 1이다.

(사이트의 중복이 허용되지 않기 때문)

N의 값은 M의 값보다 크면 안 된다.

 

 

첫 입력은 경우의 수를 만들 케이스의 개수

다음 입력부터 경우의 수를 만들 N, M값 입력

 

 

출력은 경우의 수

 

 

---

 

과정을 한 번 생각해 보도록 하겠습니다.

 

 

순열 예시

 

수학에서 흔히 예로 드는 것은 전체 학생 수에서 임원을 뽑는 경우의 수입니다.

 

전체 학생수 (M) = 4

반장 1명 부반장 1명 (N) =2

 

 

반장과 부반장은 역할이 다르기에 같은 분류라고 할 수 없습니다.

즉 각각의 인원이 반장이 될 경우와 부반장이 될 경우가 상이하다는 뜻이며

이는 순서에 의존을 해야 한다는 뜻입니다.

 

 

파란색 기준  ㅁ = 반장   ㅇ = 부반장

 

 

노란 원이 학생입니다.

첫 번째 원의 학생이 반장이 되는 경우의 수와 부반장이 되는 경우의 수는 완전히 상이합니다.

 

 

위의 총 경우의 수에서는 겹치는 부분이 존재합니다.

그 값들을 제외해 주면 구하려는 값이 나오며

 

 

이는 공식으로 m! / (m-n)! 로 명시되어 있습니다.

 

 

즉 4명의 학생으로 반장 1명 부반장 1명 선별할 경우의 수

4! / (4-2)! = 12입니다.

 

---

조합 예시

 

학생 4명(M)은 같습니다. 하지만 이번에는 청소당번 2명(N)을 정합니다.

 

 

청소당번은 똑같은 역할입니다. 언제 걸리든 청소합니다.

즉 이는 순서의 의존을 받지 않습니다.

 

파란색 기준 ㅇ = 청소당번

 

 

첫 번째 학생이 처음으로 당번에 걸리든 두 번째로 당번이 걸리든

일단 당번 걸리면 고통 시작입니다.

 

 

이는 첫 번째 학생이 당번에 걸렸을 경우

나머지 한 명이 당번에 걸릴 확률(3)만 계산하면 되는 의미입니다.

 

 

이를 공식으로 나타내면

 

m! / (m-n)! / n!

4! / 2! / 2! = 6

 

---

결론

 

다리를 놓는다는 개념은 쉽게 말해서 청소당번을 뽑는 경우와 같습니다.

동쪽 다리 = 학생 수, 서쪽 다리 = 청소당번

 

 

동쪽의 1사이트가 서쪽의 1 사이트에 다리 놓는 거랑

2 사이트에 다리 놓는 거랑 큰 의미가 없다는 뜻입니다.

같은 다리를 놓기 때문입니다.

 

---

코딩

 

파이썬에서 math 모듈을 지원하며 수학함수를 활용할 수 있습니다.

문제에서 주로 사용하는 것은 팩토리얼(!)이기 때문에 factorial 함수를 불러와 사용하였습니다.

 

from math import factorial as fac

 

 

'as fac'을 통해 factorial함수를 fac로 줄여 사용했습니다.

 

 

 

백준 1010 최종본

 

---

코드 해석

 

 

#1 = 오류처리 부분입니다. N값이 M값보다 크면 난처해집니다.

(학생이 4명인데 당번 5명을 뽑으라 하면...ㅎ)

그래서 에러처리로 0을 출력하도록 했습니다.

 

 

#2 = N과 M의 값이 같을 경우 무엇이든지 1입니다.

이는 순서에 의존을 하지 않기 때문입니다.

 

 

#3 = 조합을 구하는 공식을 코드화 한 것입니다.

 

 

 

결과

 

 

-끝-