[Baekjoon] 6187_Going to the Movies

문제(출처: https://www.acmicpc.net/problem/6187)

---

< Going to the Movies >

 

문제 풀이 

 

소를 데려갈 수 있는 모든 경우의 수를 확인하며 그중에서 가장 무거운 소 그룹의 무게를 구한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _6187_ { // Going to the Movies
	static int result, C;
	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		C = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());

		arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
		}

		result = 0;
		recursion(0, 0);

		System.out.println(result);
	}

	private static void recursion(int idx, int sum) {
		if (idx >= arr.length) {
			return;
		}
		if (sum + arr[idx] <= C) {
			result = Math.max(result, sum + arr[idx]);
			recursion(idx + 1, sum + arr[idx]);
		}
		recursion(idx + 1, sum);
	}
}

변수)
C, N : 트럭 용량, 소 마릿수
arr : 소 무게
result : 가장 무거운 소 그룹의 무게

 

트럭 용량과 소 마릿수를 입력받는다. N만큼 소 무게를 입력받아 배열 arr에 저장한다. recursion 함수를 호출한 후 가장 무거운 소 그룹의 무게 result를 출력한다.

 

recursion (int idx, int sum)

1) idx가 배열 길이보다 크다면 더 이상 계산할 것이 없으므로 종료

2) sum과 배열 idx번째 값의 합이 C 이하라면 소를 더 데려갈 수 있으므로 result를 최댓값으로 업데이트 및 recursion 함수 호출

3) idx번째 소를 데려가지 않는 경우를 구하기 위해 합을 구하지 않고 recursion 함수 호출

---

---