동적계획법27 [백준/C,C++] 12865번: 평범한 배낭 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 예제 입력으로 바로 설명드리겠습니다. 물건의 수는 4이고, 버틸 수 있는 무게는 7입니다. 각 물건의 무게와 가치는 6/13, 4/8, 3/6, 5/12 입니다. 배낭 무게 1 배낭 무게 2 배낭 무게 3 배낭 무게 4 배낭 무게 5 배낭 무게 6 배낭 무게 7 물건1 (6/13) 0 0 0 0 0 13 13 물건2 (4/8) 0 0 0 8 8 .. 2021. 3. 8. [백준/C,C++] 1912번: 연속합 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net DP 문제 중 정말 간단하다 느꼈던 문제입니다. 당장 예제입력인 10 -4 3 1 5 6 -35 12 21 -1 수열을 살펴보겠습니다. 10 -4 3 1 5 6 -35 12 21 -1 연속합 10 6 9 10 15 21 -14 12 33 32 이전 연속합에 현재 입력값을 더한 값과 입력값 중 큰 값을 갱신해주면 됩니다. #include using namespace std; #define MAX 100001 int DP[M.. 2021. 3. 8. [백준/C,C++] 9251번: LCS www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 꽤 많이 애먹었던 문제입니다. 결국 다른 분의 해답을 참고하여 다시 풀어봤지만.. 다음에 이 문제를 다시 풀어본다고 해도 바로 해답이 떠오를 것 같지 않습니다.. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K 1 2 3 3 4 4 2차원 배열을 통해 문제를 해결해야.. 2021. 3. 8. [백준/C,C++] 2565번: 전깃줄 www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net hackids.tistory.com/26 [백준/C,C++] 11053번: 가장 긴 증가하는 부분 수열 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인.. hackids.tistory.com 언뜻 보면 잘 모를 수.. 2021. 3. 8. 이전 1 2 3 4 5 6 7 다음
