Algorithm/Dynamic Programming
-
백준 12865 - 평범한 배낭Algorithm/Dynamic Programming 2024. 3. 22. 13:15
12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배..
-
백준 1256 - 사전Algorithm/Dynamic Programming 2024. 3. 15. 17:50
1256번: 사전 (acmicpc.net) 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 문제 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다. 규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완..
-
백준 1082 - 방 번호Algorithm/Dynamic Programming 2024. 1. 25. 09:44
1082번: 방 번호 (acmicpc.net) 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 이번주에 알고리즘 공유 문제는 방 번호 문제이다. 이 문제는 dynamic programming과 Greedy Algorithm을 모두 떠올려야하는 문제로 점화식 작성을 할 때 Greedy를 생각하지 않으면 쉽사리 작성할 수 없는 문제이다. 문제를 먼저 이해해보자. 예제 입력 1 복사 3 6 7 8 21 예제 출력 1 복사 210 이렇게 6 7 8 을 입력받게 될 때 방 번호는 각각 0 1 2가 될 것이다. 방 가격 : 6 7 8 방 번호 : 0 1 2 이런 모습이 나오게 되는데 여기서 ..