[PS] 백준#1010 다리 놓기 / 파이썬
알고리즘 문제 풀이
- 문제 : 다리 놓기
- 해결 :
solved
- 분류 : 조합, DP
풀이 방법(1) - 조합
- 조합 공식을 사용한다
- n!이 사용되는데 여기서 DP로 n까지의 n! 각 값들을 배열을 이용해 구해놓는다.
- dp로 만들어 놓은 배열을 이용하여 공식에 따라 계산한다.
풀이 방법(2) - DP
- n까지의 배열을 초기화하고 각 인덱스는 x개의 동쪽 사이트가 있을 경우로 정의한다.
- dp[i] 는 i번째 사이트를 포함하는 경우의 수 + 포함하지 않는 경우의 수
f(n, k) = f(n-1, k) + f(n-1, k-1)
- dp 배열의 마지막 원소를 출력한다.
소스코드
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
dp = [[1] * (M+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, M+1):
if i > j :
dp[i][j] = 0
elif i == j :
dp[i][j] = 1
else:
dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
print(dp[-1][-1])
Author And Source
이 문제에 관하여([PS] 백준#1010 다리 놓기 / 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@su-ram/PS-백준1010-다리-놓기-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)