728x90 다이나믹프로그래밍30 [python] 백준 4811 알약 https://www.acmicpc.net/problem/4811 문제 해결DP를 이용해야하는 문제라는 것은 쉽게 알 수 있다.그런데 DP를 어떻게 활용할지는 생각보다 어렵다.힌트는 알약이 $n$개가 있으면 H가 $n$번 W가 $n$번 써진다는 사실이다.그래서 dp[i][j]를 H가 $i$번, W가 $j$번 썼다는 것으로 정의한다.j가 1~n일 때 dp[0][j]는 1이다.그리고 dp[i][j] += dp[i-1][j] + dp[i][j-1]이다. CODEimport sysinput = sys.stdin.readlinedef DP(n): dp = [[0 for _ in range(n+1)] for _ in range(n+1)] for i in range(1,n+1): dp[0][i.. 2024. 6. 2. [python] 백준 16565 N 포커 https://www.acmicpc.net/problem/16565 문제 해결DP를 이용해 n개중 m개를 뽑았는데 그중 k개 종류가 나올 경우의 수를 dp[m][k]라고 정의한다.dp[0][0]은 1로 정의그러면 $ dp[i][j] = \sum_{k=0}^{3} \binom{4}{k} \times dp[i-k][j-1]$ 이후 포카드가 나올 수 있는 경우의 수를 계산하기 위해idx (포카드 나오는 개수)$ ans += \binom{13}{idx} * dp[n-4*idx][13-idx]$ CODEimport sysinput = sys.stdin.readlineimport mathmod = 10007def combination(n, r): return math.factorial(n)//(math... 2024. 5. 23. [python] 20188 등산 마니아 https://www.acmicpc.net/problem/20188 문제 해결트리와 DFS를 사용해야한다는 것은 쉽게 알 수 있지만 어떻게 활용할지 매우 어려운 문제https://youtu.be/AQzKDzQqIRE다음 동영상을 봐도 어렵다... CODEimport sysinput = sys.stdin.readlinefrom collections import deque, defaultdictsys.setrecursionlimit(10**8)def dfs(cur, parent): global ans for child in graph[cur]: if child != parent: dfs(child, cur) dp[cur] += dp[ch.. 2024. 5. 22. [python] 백준 1750 서로소의 개수 https://www.acmicpc.net/problem/1750 1750번: 서로소의 개수 예제 1의 경우 가능한 경우의 수는 (2, 3), (4, 3), (2, 4, 3)이다. www.acmicpc.net 문제 해결 dp[i]를 최대공약수를 i로 가지는 경우의 수라고 정의하면 문제풀이는 끝이다. 미리 입력 값을 받아놓은다음 하나씩 돌아가며 dp[A[i]] += 1 해야한다. 각 입력값을 1부터 Maximum(입력값의 최댓값)까지 수 j를 돌면서 dp[(입력값과 j의 최대 공약수)] += dp[j]를 한다. CODE import sys input = sys.stdin.readline mod = 10000003 import math n = int(input()) A = [int(input()) for _.. 2024. 2. 22. 이전 1 2 3 4 ··· 8 다음 728x90
