[백준] 18429번 근손실 (JAVA)

문제

- 현재 3대 운동 중량 500

- 하루가 지날 때마다 중량이 K만큼 감소

- N개의 서로 다른 운동 키트 보유

- 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가

- 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고 이 경우의 수를 출력

 

해결방법

운동 키트 적용 순서를 순열을 이용하여 정하고, 적용 순서가 정해지면 하루하루 중량이 감소하고 운동을 통해 보충한 중량 증가량을 계산하여 500 이상을 유지하는지를 확인할 수 있도록 하였다. permutation 함수를 이용하여 순열을 통해 운동 키트 적용 순서를 짰고, N개(운동 키트 개수)만큼 순서를 짰다면 중량을  계산하여 조건에 따라 경우의 수를 계산하였다.

 

코드

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

public class Main {
    static int N, K, result = 0;
    static int[] fitness, order;	// 입력 받은 운동 키트, 운동 키트 적용 순서
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        fitness = new int[N];
        order = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            fitness[i] = Integer.parseInt(st.nextToken());
        }

        permutation(0, new boolean[N]);

        System.out.println(result);
    }

    // 운동 키트 적용 순서를 짤 순열 함수
    static void permutation(int cnt, boolean[] isChecked){
        운동 키트 개수만큼 뽑았을 때, 조건 만족 여부 확인
        if(cnt == N){
            int weight = 500;
	
    	    // 하루에 근손실 양과 운동을 통해 보충한 양을 계산하여 500 이상인지 확인
            for(int i = 0; i<N; i++){
                weight -= K;
                weight += order[i];
                if(weight < 500) return;
            }
	    // 500을 넘는다면 경우의 수 +1
            result++;
        }
	
    	// 순열 알고리즘
        for(int i = 0; i<N; i++){
            if(isChecked[i]) continue;

            order[cnt] = fitness[i];
            isChecked[i] = true;
            permutation(cnt + 1, isChecked);
            isChecked[i] = false;
        }
    }
}