-
[알고리즘] 백준 1010 다리놓기알고리즘 2022. 10. 22. 13:13728x90
1. 문제
https://www.acmicpc.net/problem/1010
2. 접근
1. 문제를 손으로 풀다보면 반복되는 연산 구조를 볼 수 있다.
2. 그 연산구조에서 2가지 방법을 볼 수 있는데, 일반적으로 수학적으로 푸는 방법, DP 로 푸는 방법이 있다.
- 수학
nCm 의 방법을 쓰면 되는데, 우리가 쓰는 combination은 보통 리스트에서 사용을 한다.
하지만, 우리는 여기서 정수로 input을 받기에 combination이 아닌, nCm = m! // ((m-n)! * n!) 이 방법을 쓰면된다
두개의 정수 n,m을 map 함수로 받아서 적용하면 된다.
참고로 factorial은 math.factorial 도 되고, factorial 험수를 만들어도 된다
참고,
def fact(n): num = 1 for i in range(1, n+1): num *= i return num
- DP
DP는 2차원 배열을 초기화 해보자
두개의 정수를 받고 그 정수를 2차원 배열의 행과 열로 하며, 0으로 초기화한다
west, east = map(int, input().split()) dp = [[0 for _ in range(east+1)] for _ in range(west+1)]
참고로 문제에서 보면 " 서쪽의 다리 개수 <= 동쪽의 다리 개수 " 임을 알고 풀자
서쪽과 동쪽의 다리의 개수가 같은지, 서쪽의 다리개수 == 동쪽의 다리 개수 인지를 2중 for문 속에서 체크를 먼저해준다
그리고 서쪽의 다리 개수 < 동쪽의 다리 개수 일때를 조심해야하는데, 초기화한 2차원 배열을 보면 dp[w][e] = dp[w][e-1] + dp[w-1][e-1] 임을 알 수 있다
for i in range(1, west+1): for j in range(1, east+1): if i == 1: dp[i][j] = j continue if i == j: dp[i][j] = 1 else: if j > i: dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
3. 풀이
# 다리 놓기 import sys input = sys.stdin.readline # def fact(n): # num = 1 # for i in range(1, n+1): # num *= i # return num # for tc in range(int(input())): # # 서쪽 -- 동쪽 사이트의 개수 # westBridge, eastBridge = map(int, input().split()) # bridge = fact(eastBridge) // (fact(eastBridge - # westBridge) * fact(westBridge)) # print(bridge) for tc in range(int(input())): west, east = map(int, input().split()) dp = [[0 for _ in range(east+1)] for _ in range(west+1)] for i in range(1, west+1): for j in range(1, east+1): if i == 1: dp[i][j] = j continue if i == j: dp[i][j] = 1 else: if j > i: dp[i][j] = dp[i][j-1] + dp[i-1][j-1] print(dp[west][east])
'알고리즘' 카테고리의 다른 글
[알고리즘] 백준 1135 - 뉴스 전하기 (0) 2022.11.03 [알고리즘] 카드 정렬하기 - 백준 1715 (0) 2022.11.02 [알고리즘] 이코테 - 1이 될 때까지 ( 2018 E 기업 알고리즘 대회 ) (0) 2022.10.18 [알고리즘] 이코테 - 큰 수의 법칙 - 2019 국가 교육기관 코테 (0) 2022.10.17 [알고리즘] 프로그래머스 - 배달 (0) 2022.10.02