백준 1010 다리놓기 (파이썬)

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

1. 문제 설명

왼쪽엔 N개, 오른쪽엔 M개의 사이트가 존재한다. 왼쪽 오른쪽 사이트를 연결하는데 겹쳐지는 건 불가능하다.

 

2. 문제 접근 (실패)

왼쪽을 기준으로 오른쪽 사이트를 연결해 보았을 때 연결할 수 있는 가짓수를 세보았다. 

왼쪽에 첫번째 사이트가 오른쪽 첫번째 사이트를 가리키고,

왼쪽 두번째 사이트가 오른쪽 두번째 사이트를 가리키고,

왼쪽 세번째 사이트가 오른쪽 세번째 사이트를 가리키면,

왼쪽 네번째 사이트는 오른쪽 4,5,6,7 사이트를 가리킬 수 있게 된다.

왼쪽 n-1번째가 오른쪽 x번째 사이트를 가리키면 왼쪽 n번째는 자동으로 오른쪽 사이트의 개수 - x 만큼의 가짓수가 생긴다.

왼쪽 n번째 사이트는 왼쪽 n-1번째 사이트에 의해서 가리킬 수 있는 사이트의 개수가 정해진다.

가짓수를 세다보면 반복해서 쓰이는 값들을 확인할 수 있다. 따라서 왼쪽 사이트를 기준으로 배열을 만든 후 왼쪽사이트가 오른쪽 i번째 사이트를 가리킬 때 가짓수를 arr배열에 저장해주고 해당 값이 또 쓰일경우 arr배열에 저장되어 있는 값을 사용했다.

def dp(w_i,e_i,arr,w_len,e_len):

    if w_i==w_len:

        return e_len-e_i

    for i in range(e_i,e_len-1):

        if arr[w_i][i]==0:

            arr[w_i][i]=dp(w_i+1,i+1,arr,w_len,e_len)

    return sum(arr[w_i][e_i:])

N=int(input())

for i in range(N):

    west,east=map(int,input().split())

    if west == 1:

        print(east)

    else:

        arr=[[0]*east for j in range(west-1)]

        dp(0,0,arr,west-1,east)

        print(sum(arr[0]))

 

dp + 재귀로 풀었더니 시간초과를 해결하지 못했다..

 

3. 문제 해결

고등학교 때 배운 조합으로 쉽게 풀렸다..!

오른쪽 사이트에서 왼쪽 사이트 개수만큼 고르기만 하면 된다. (왼쪽 사이트와 오른쪽 사이트 개수가 같다면 겹치지 않게 연결할 방법은 하나뿐이므로)

오른쪽사이트 C 왼쪽사이트

N=int(input())

    for i in range(N):

        west,east=map(int,input().split())

        tot1,tot2=1,1

        min_val=min(west,east-west)

        if min_val == 0:

            print(1)

        else:

            for i in range(east-min_val+1,east+1):

                tot1*=i

            for i in range(1, min_val+1):

                tot2*=i

            print(tot1//tot2)