728x90 다이나믹프로그래밍27 [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. [python] 백준 23258 밤편지 https://www.acmicpc.net/problem/23258 23258번: 밤편지 $C = 3$일 때, 1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점 www.acmicpc.net 문제 해결 DP의 전형적인 문제이다. 우선 $\sum_{i=1}^{i=C-1} 2^{i} k일 때에 DP[k][i][j]이면 지날 수 없다. 하지만 지날.. 2024. 2. 18. [python] 백준 2092 집합의 개수 https://www.acmicpc.net/problem/2092 2092번: 집합의 개수 1부터 T까지의 범위에 있는 수들이 총 A개 있다. 이들 중 K개를 골라서 집합을 만들 때, 가능한 집합의 개수를 세려 한다. 단, K의 범위는 1 ≤ S ≤ K ≤ B ≤ A로 한다. 즉, 두 정수 S, B를 입력받아서 www.acmicpc.net 문제 해결 각 숫자의 개수를 알 수 있도록 numbers[num]을 통해 개수를 저장한다. dp[i][j] 를 i까지 숫자중 j개 사용했을 때 가지수를 나타내는 dp함수를 만든다 기본적으로 숫자 i가 k개 있을 때 k개이하를 쓸 수 있으므로 dp[i][j] += 1씩 해준다. (j=k 일때 dp[i][j] += dp[i-1][j-k]이다. 숫자를 1000000으로 나눠.. 2024. 2. 9. [python] 백준 1943 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 문제 해결 먼저 돈의 총 합을 보았을 때 홀수이면 나눌 수 없다는 것을 알 수 있다. 짝수여도 무조건 가능한 것은 아니지만 총합의 절반을 나눌 수 있다. 절반을 가지고 가지고 있는 동전을 조합하여 맞출 수 있는가?를 보면 된다. 이는 DP를 가지고 풀 수 있다. 처음에는 이론상 0원만 가능하고 동전의 종류별로 채워나가며 dp[total]이 True가 된다면 만들 수 있는 것이다. 만.. 2024. 2. 7. 이전 1 2 3 4 ··· 7 다음 728x90
