728x90 수학33 [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] 백준 2635 수 이어가기 https://www.acmicpc.net/problem/2635 2635번: 수 이어가기 첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다. www.acmicpc.net 문제 해결 첫 번째 수가 주어지고 두 번째수는 첫번째 수 이하인 부분들을 반복해나가면서 최적의 수를 찾아야한다. 사실 재귀를 사용해서 최대 길이를 찾는 것은 어렵지 않다. 하지만 문제를 잘 읽어야하는게 이후 나오는 수들은 0이여도 상관이 없다는 것이다.(음이 아닌 수이기 때문) 문제 난이도는 쉬운 편 CODE import sys input = sys.stdin.readline def dfs(A:list): global target, ans if A[-2] - A[-1] >= 0: A.append(A[-2] .. 2024. 4. 18. 이전 1 2 3 4 ··· 9 다음 728x90
