다이나믹프로그래밍

문제출저 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main_B_2098_외판원순회 { static int n; static int[][] boa..

문제출저 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제풀이 배낭 문제, 냅색 알고리즘 문제로 조합 최적화를 찾아야 한다. 허용치 k인 배낭에 무게 w의 물건들을 담아서 물건들의 가치 v가 가장 높은 경우를 구해야한다. 문제를 해결하기 위해 2차원 int 배열인 dp를 활용한다. 2차원 배열인 dp의 가로줄은 배낭의 무게, 세로줄은 아이템을 배치한다. 1 2 3 4 5 6 ..

문제출저 https://www.acmicpc.net/problem/1480 1480번: 보석 모으기 첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보 www.acmicpc.net 문제풀이 주어진 가방을 이용해 최대한 많은 보석을 담는 방법을 구하는 문제이다. 이를 위해 중복을 줄여주는 비트마스크와 다이나믹프로그래밍, 완전탐색을 위한 DFS를 활용한다. int MAX = 14; dp = new int[1

문제출저 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /* https://sangbeomkim.tistory.com/84 */ publ..