[백준]_1010번 : 다리 놓기(파이썬 and C언어)

 

1010번: 다리 놓기

 

문제풀이의 방향

처음 이 문제를 접했을 때 백준에 제시된 그림을 통해 경우의 수를 세는 문제임을 파악할 수 있다. 해당 그림을 보고 바로 들었던 생각은 강 서쪽(정의역) -> 강 동쪽(치역)과 같이 현재 상황을 일대일대응 함수로 치환할 수 있다는 것이다. 고등학교 수학(하)교육과정은 바뀌기 때문에 만약 이 글 작성 시점 이후로 순열과 조합이 수학(하)에 들어있지 않다면 필자를 틀이라 생각하고 넘어가주길 바란다..에 배정되어 있는 순열 또는 조합을 활용하는 문제이다. 하지만 서쪽에서 시작하는 다리에 순서가 상관없으므로 순열 대신 조합을 사용해야 함을 알 수 있다. 

---

사용하는 수학적 모델

답을 도출해 내려면 그냥 간단하게 M개 중에서 N개를 지정하는 경우의 수를 구하면 되는 것이다. 따라서 우리가 이용할 수학적 틀은 조합의 공식인 

 

M! / (M-N)!N!  이다. 

---

전략

사용자로부터 M과 N을 입력받고 위의 조합 공식(M! / (M-N)!N!)에 대입해서 답을 도출하면 된다!!

---

시도 1 (Python)

testcount=int(input())
arrn=[]
arrm=[]
result=[]
i=1
def factorial(n):
    if n>1:
        return n*factorial(n-1)
    else:
        return 1
for c in range(1, testcount+1):
    a,b=map(int, input().split())
    arrn.append(a)
    arrm.append(b)
while i<testcount+1:
    t=arrm[i-1]-arrn[i-1]
    M_N=factorial(t)
    M=factorial(arrm[i-1])
    N=factorial(arrn[i-1])
    result.append(M/(M_N*N))
    i+=1
for k in range(1,testcount+1):
    print(int(result[k-1]))

<평가>

백준에서 정답으로 인정해주기는 하지만 필요 없는 부분들이 있기 때문에 대체적으로 난잡하다. 하나하나씩 손봐주면서 더 간결한 코드로 만들어보자.

---

팩토리얼 함수

재귀를 배우면서 아마 가장 대표적으로 연습하는 것이 팩토리얼 계산일 것이다. 따라서 재귀함수를 만들어주면 다음과 같다.

def factorial(n):
    if n==1 or n==0:
        return 1
    return n*factorial(n-1)

반면 재귀를 사용하지 않고 그냥 순수히 곱하는 방법은 다음과 같다.

def factorial(n):
    num=1
    for i in range(1, n+1):
        num*=i
    return num

아무거나 사용해도 무방해 보인다.

 

배열이 필요 없는 이유

백준이 보여주는 대로 입력과 출력을 굳이 따로 출력하지 않아도 된다. 입력을 받자마자 결과를 출력해도 너그럽게봐준다.

따라서 굳이 배열에 저장한 상태로 출력을 할 필요성이 없어지므로 아주 간결하게 최종 코드가 정리된다.

import sys
input=sys.stdin.readline

def factorial(n):
    if n==1 or n==0:
        return 1
    return n*factorial(n-1)
    
cnt=int(input())
for _ in range(cnt):
    N, M = map(int, input().split())
    print(int(factorial(M)/(factorial(M-N)*factorial(N))))

---

추가 정리

문제가 안 풀릴 때 질문게시판을 둘러볼 때 아니면 구글에서 복붙 할 때 import sys, input=sys.stdin.readline 이 거의 디폴트로 깔려 있음을 알 수 있다. 그렇다면 sys가 input보다 뭐가 좋다고 다들 쓰는 것일까?

 

 사실 input과 sys.stdin.readline이 하는 역할은 같아 보여도 가장 중요한 차이점이 있는데 이것은 바로 input은 입력받은 문자열에 rstrip() 함수를 적용하고 리턴하는 대신 sys.stdin.readline은 이 단계를 건너뛴다그래서 귀찮을 때가 있다. 즉 시간을 조금이라도 줄이려면 아래와 같은 코드를 처음에 작성하고 들어가야 하는 것이 유리하다.

import sys
input=sys.stdin.readline

---

시도 2(C 언어)

"이제 파이썬으로 짰으니 c언어로 바꾸기만 하면 되네!!" 라는 무척이나 무책임한 생각을 하면 안 된다. 왜냐하면 파이썬에서 신경 쓰지 않아도 되는 디테일들을 c언어에서는 철저하게 지켜야 하기 때문이다. 즉 앞에서 파이썬으로 짠 방식대로 특정 수의 팩토리얼을 직접 구해버리는 연산을 해버리면 아무리 c언어에서 지원하는 가장 큰 정수형 구조(long long)를 갖고 와도 M!, N! 의 최댓값인 8841761993739701954543616000000에 명함을 내밀지도 못한다. 

 

전략의 변화

변수형 크기의 오버플로를 방지하고자 분자의 M! 을 하나씩(M!=1*2*3*...) 계산하는 동시에 분모의 팩토리얼 2개도 마찬가지로 같이 계산해 준다. 먼저 식을 간단하게 해 주기 위해 분모의 두 팩토리얼 중 N! 만 남기고 나머지를 모두 약분해 준다. 즉 분자는 M, M-1, M-2 ... M-(N-1) [N개의 항], 분모는 1, 2, 3 ... N-1 [N개의 항]으로 나타나게 되므로 반복문을 이용하면 다음과 같이 나타낼 수 있다.

#include<stdio.h>
int main()
{
	int cnt, N, M;
	scanf("%d", &cnt);
	for (int i = 0; i < cnt; i++)
	{
		int ans = 1;
		scanf("%d %d", &N, &M);
		for (int j = 0; j < N; j++)
		{
			ans *= M - j;
			ans /= (j + 1);
		}
		printf("%d\n", ans);
	}
	return 0;
}