Baekjoon_1010_bridge python 풀이

 

 

 

import sys

input = sys.stdin.readline




T = int(input())


result = [[0] * 31 for _ in range(31)]

for j in range(1,31) :
    for k in range(j,31) :
        if j == k :
            result[j][k] = 1
        elif j == 1 :
            result[j][k] = k
        else:
            answer = 0
            for l in range(j-1,k):
                answer += result[j-1][l]
            result[j][k] = answer
                

for i in range(T) :
    bridge = list(map(int,input().split()))
    
    west = bridge[0]
    east = bridge[1]
    print(result[west][east])

간단한 DP 문제이다.  더간단히 풀수있을지 모르겠지만 익숙해지려고 푼 문제이다.

 

1. result[n][m]가  n 개의 사이트 m개의 사이트가 있을때의 빈공간(리스트)을 만들어준다.

2. n사이트와 m의 사이트가 같으면 1대1 한종류밖에 성립안하므로 if j == k 는 result[j][k] =1 을  해주고

3. else문은  답을 넣어줄 answer 생성후 for 문으로 합을 더해준다 아래와 같이 그림을 그려서 설명하면 

 

n = 3 , m =4 일 때 

첫번째 사진 처럼 n의 첫번째가 m의 첫번째를 가리킬 때  나머지 꺼로보녀 n= 2 대 m = 3 일때 
경우의수인것을 알수있다. 

또한 2번째사진처럼 n의 1번째가  m의 2번째를 가리키면

3번째 사진처럼 n= 3  m =3  으로 1대1 대칭이된다. 이것을 보고

result[3][4] = result[2][3] + result [3][3]  인것을  알 수 있다.



헷갈린다면 더큰수로 테스트해보면 알수 있지만



result[n][m] 은  result[n-1][(n-1)~m]의 합인것을 알수있다. 그것을 표현한게 위와같은 for문이다.

 

4. 입력을 받고 result 값에서 찾아주면 된다.