[Baekjoon] 18429_근손실

Silver III

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

---

< 근손실 >

 

문제 풀이 

 

조합을 사용하여 모든 경우의 수를 확인한다. 확인하면서 500 미만이 되는 경우 다음 조합을 확인한다.

 

 my solution (Java)

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

public class _18429_ { // 근손실
	static int arr[], answer;
	static boolean visited[];

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

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		arr = new int[n];
		visited = new boolean[n];
		answer = 0;

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

		search(0, n, k, 500);

		System.out.println(answer);
	}

	private static void search(int idx, int n, int k, int w) {
		if (idx == n) {
			answer += 1;
			return;
		}
		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				if (w + arr[i] - k < 500) {
					continue;
				}
				visited[i] = true;
				search(idx + 1, n, k, w + arr[i] - k);
				visited[i] = false;
			}
		}
	}
}

 

변수)
n, k : 운동 키트 수, 감소하는 중량
arr : 운동 키트 중량 증가량
visited : 조합에서 사용할 방문 여부
answer : 항상 중량이 500 이상이 되도록 하는 경우의 수 

 

운동 키트 중량 증가량을 n일 동안 어떤 순서로 적용할지 조합을 사용한다. 조합을 사용하여 어느 순간 중량이 500보다 작아지면 정답이 될 수 없으므로 다음 조합을 확인한다. n일 동안 항상 500 이상을 유지한다면 answer +1을 해준다.

---

---