백준 18429 - 근손실

Java

18429 번 - 근손실

문제

접근 방법

근손실을 방지해야한다.
DFS의 순열을 사용하여 N일 동안 사용할 키트의 순서를 정한다.
순서가 정해질 때 마다, 운동을 진행하여 근손실을 발생하는지 확인하여 미발생시 결과값을 증가시킨다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result, k;
	static int[] sel, arr;
	static boolean[] vis;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());

    	sel = new int[n];
    	arr = new int[n];
    	vis = new boolean[n];

    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(stk.nextToken());
    	}

    	DFS(0);

    	System.out.println(result);
    	br.close();
	}
	// 사용할 운동 키드들의 순서를 정한다.
	private static void DFS(int lv) {
		if(lv == n) {
			// 근 손실이 발생하지 않으면, 해당 순서를 결과값에 더 한다.
			if(doExercise()) {
				result++;
			}
			return;
		}

		for(int i = 0; i < n; i++) {
			if(!vis[i]) {
				sel[lv] = arr[i];
				vis[i] = true;
				DFS(lv + 1);
				vis[i] = false;
			}
		}
	}
	// 운동 시작
	private static boolean doExercise() {
		int weight = 500;

		for(int i = 0; i < n; i++) {
			weight += sel[i];
			weight -= k;
			// 운동 중, 근손실이 발생하였을 때
			if(weight < 500)
				return false;
		}

		return true;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}