[코딩풀이] - BAEKJOON.1010 다리놓기

---

코딩 풀이를 시작하며

---

  코딩 풀이에 있어서 사전지식이나 코딩 실력이 뛰어나게 준비되어 있는게 아닌 공부를 해가며 풀이를 작성하는 것이라 최대한 문제 풀이에 대해 생각한 것들을 흐름대로 적으려고 한다. 하나하나 천천히 이해해가면서 풀이를 해나간다면 충분한 실력이 쌓일거라 기대하며 글을 시작해보겠다.

---

문제 1010. 다리놓기

---

  재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

 

  재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

---

풀이 과정

---

  다리 끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하라고 했다. 중고등학교 때 어렴풋이 배웠던 순열, 조합을 떠올렸다. 정말 어렴풋이 기억이 났기 때문에 검색을 통해 순열과 조합에 대해 간단히 되짚었다.

  문제의 그림을 먼저 생각해보자. 강 동쪽에는 7개의 사이트가 있고 강 서쪽에는 4개의 사이트가 있다. 한 사이트에는 최대 한 개의 다리만 연결될 수 있고 서쪽의 사이트 개수만큼 다리를 지으려고 한다고 믄제에 명시 되어 있다. 이것은 7개 중에서 4개를 뽑는 경우의 수를 구하는 것,  즉, 조합을 구하는 것이다.

 

  문제를 어떻게 풀어야 하는지 파악을 했으니 코드를 작성해볼 차례이다. 조합의 핵심인 팩토리얼을 구현한다.

def facto(n):
    a = 1
    for i in range(n):
        a = a * (i+1)
    return(a)

- a를 1로 초기화 한다.

- 0부터 n까지 반복하는 for문을 작성한다.

- a와, i에 1을 더한 값을 곱하고 그 값을 a로 지정한다.

- a를 리턴한다.

---

   입력의 첫 줄에는 테스트 케이스 개수 T가 주어진다는 입력 요구사항이 있다. T라는 변수에 입력값을 받도록 하고 그 수 만큼 입력을 받고 그 입력에 대한 결과를 도출하면 된다.

T = int(input())

for i in range(T):
    a, b = map(int,input().split(' '))

    if b == 0 :
        print(0)
    else:
        a_res = int(facto(a))
        b_res = int(facto(b))
        a_b_res = int(facto(b-a))

        print(int(b_res // a_res // a_b_res))

- a와 b를 int타입으로 입력을 받는다.

- b가 0일 경우 0을 출력한다.

- 0이 아닐 경우 조합을 구한다.

 

  7개 중에서 4개를 고르는 경우의 수 = 7C4로 생각할 수 있다. 여기서 조합 공식을 떠올려 보자.

nCr

= nPr / r! 

       - nPr = n! / (n-r)! 이므로

= n! / r! * (n-r)!

  이제 공식에 대입을 하면 7! / 4! * (7-4)! 라는 결과를 도출해 낼 수 있다. 단순히 수학 공식을 푸는 것이었다면 수식을 약분하여 답을 얻어내면 되지만, 우리는 어떠한 값을 입력을 받아도 결과를 도출할 수 있도록 코드를 작성해야 한다. for문에서 a와 b를 입력을 받았고 (0<N<=M<30)이라는 조건이 있으므로 M이 공식의 n값, N이 r값으로 생각할 수 있다. 7! / 4! * (7-4)! 의 식에서 생각해보면 b! / a! * (b-a)! 이다.

 

  앞서, 입력한 값의 팩토리얼 값을 구하는 def facto()함수를 구현했다. 0이 아닐 경우 조합을 구하는 구문에서 facto()함수를 이용하여 b의 팩토리얼, a의 팩토리얼, (b-a)의 팩토리얼 값을 변수에 지정한 후, 공식에 맞게 대입 후 출력하면 코드는 완성이 된다.

---

또 다른 풀이

---

  다른 사람들의 풀이를 참고해보았더니 실행 속도가 더 빠르게 실행된 코드가 있었다.

import sys
input = sys.stdin.readline

t = int(input())
factorials = [1, 1]
for i in range(2,30):
    factorials.append(factorials[-1]*i)

for _ in range(t):
    n, m = map(int, input().split())
    print(factorials[m]//factorials[n]//factorials[m-n])

  배열의 마지막 값에 2부터 30까지 증가하는 i를 곱하여 팩토리얼의 결과를 배열에 append해서 아예 팩토리얼 값을 저장하는 배열을 만들어 준 모습이다. 팩토리얼의 인덱스를 입력값으로 받는 방식이었다. 이 코드를 보면서 하나 더 알아낸 것은 실행속도에 있어서 input()과 sys.stdin을 사용하는 방식이 차이가 난다고 한다.