[Python] 백준 1010번 - 다리 놓기

공부

 

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

---

표준 입력을 위해 sys 모듈 추가.

테스트 케이스 수 입력.

import sys


input = sys.stdin.readline
t = int(input())

 

왼쪽 사이트와 오른쪽 사이트의 최대 개수는 30개.

31 x 31 크기를 갖는 2차원 리스트 생성.

=> 인덱스와 번호를 일치시키기 위해 1개의 행과 1개의 열을 추가로 생성.

=. 행은 왼쪽 사이트, 열은 오른쪽 사이트를 의미.

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

 

왼쪽 사이트의 수가 1개이고 오른쪽 사이트 개수가 1개에서 30개까지 있을 때 나올 수 있는 경우의 수는 오른쪽 사이트의 개수만큼.

해당 경우를 반복문을 이용하여 초기화.

for i in range(1, 31):
    arr[1][i] = i

 

왼쪽 사이트와 오른쪽 사이트의 개수가 동일할 때 경우의 수는 1개.

2행부터 30행까지, i행부터 30열까지 반복.

- i행 j열의 값은 다음과 같이 정해짐.

=> 행 번호와 열 번호가 같은 경우(사이트 개수가 같은 경우) 1.

=> 아닌 경우 [i-1][j-1] 번째 값과 [i][j-1] 번째 값의 합.

for i in range(2, 31):
    for j in range(i, 31):
        arr[i][j] = 1 if i == j else arr[i-1][j-1] + arr[i][j-1]

 

테스트 케이스 수 만큼 반복.

- 왼쪽 사이트(n), 오른쪽 사이트(m) 수 입력받음.

- 리스트의 [n][m]번째 항 값 출력.

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

 

전체 코드.

import sys


input = sys.stdin.readline
t = int(input())
arr = [[0] * 31 for _ in range(31)]

for i in range(1, 31):
    arr[1][i] = i

for i in range(2, 31):
    for j in range(i, 31):
        arr[i][j] = 1 if i == j else arr[i-1][j-1] + arr[i][j-1]

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