728x90 배낭문제3 [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] 백준 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. [python] 백준 7579 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 해결 용량 M을 줄여야하는데 $A_{i}$ 바이트와 줄이는데 비용 $C_{i}$가 주어졌다. 이 때 최소비용을 구하는 문제 이는 배낭 문제라고 한다. https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C dp[i][j]를 i번째 물건까지 봤을 때 j요금 이하로 만들 수 있는 줄일 수 있는 메모리 합을 이야기한다. j가 i번째 메모리 사용할 때 비.. 2023. 11. 26. 이전 1 다음 728x90
