배낭1 #1535 안녕 이번 문제는 효율적으로 풀려면 백팩 알고리즘을 이용하셔야 합니다. 백팩 알고리즘은 유명한 문제로, 일반적으론 결정 트리를 이용해서 예측 값이 가장 좋은 것을 먼저 선택해서 처리합니다. 그리고 결정된 값보다 나쁜 것은 제거함으로써 그나마 빠르게 계산할 수 있습니다. https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 문제 자체는 Silver II 문제입니다. 배낭 문제로 해석을 하자면 99만큼의 무게를 넣을 수 있는 배낭에 무게 \(h_i\)이고 .. 2022. 9. 2. 이전 1 다음
