SWEA2 [SWEA/D3/DP/자바] 0/1 Knapsack 💡 문제 민수에게는 1번부터 N번까지의 번호가 부여된 N(1≤N≤100)개의 물건과 최대 K(1≤K≤1000) 부피만큼을 넣을 수 있는 가방이 있다.1번 물건부터 N번 물건 각각은 부피 Vi와 가치 Ci 를 가지고 있다. (1≤Vi, Ci≤100)민수는 물건들 중 몇 개를 선택하여 가방에 넣어서 그 가치의 합을 최대화하려고 한다.단, 선택한 물건들의 부피 합이 K 이하여야 한다.민수가 가방에 담을 수 있는 최대 가치를 계산하자 ⌨ 입력 첫째 줄 : 테스트 케이스 수(T)각 테스트 별 : 물건의 수(N) 가방의 부피(K) 주어진다.이후 N개의 줄 : 부피(Vi), 가치(Ci) 💻 출력 / 제한 각 테스트 케이스 마다 담을 수 있는 최대 가치를 출력한다. (케이스당 0.2초) 풀이 방법 nap.. 2024. 5. 16. [SWEA/D3/DFS/자바] 최장 경로 💡 문제 N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하자.정점의 번호는 1번부터 N번까지 순서대로 부여되어 있다.경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며, 경로 상의 인접한 점들 사이에는 반드시 두 정점을 연결하는 간선이 존재해야 한다.경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다. ⌨ 입력 첫째 줄 : 테스트 케이스 수 (T)둘째 줄 : 각 테스트 케이스의 N, M ( 1 M개의 줄 : 그래프 간선 정보 x y ( 1 💻 출력 / 제한 그래프에서의 최장 경로의 길이를 출력한다. / 1개 테스트 케이스 당 0.2초 풀이 방법 최장 경로의 뜻을 몰랐다. 코딩 테스트라 생각하고 입력을 보고 유추 해본 결과, .. 2024. 5. 10. 이전 1 다음
