[JAVA] 백준 18429번: 근손실

<문제>

https://www.acmicpc.net/problem/18429

18429번: 근손실

package silver;

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

//근손실
public class P18429 {
	static int n; //n일동안
	static int k; //하루가 지날때마다 감소하는 중량
	static int increase[];  //운동키트의 중량 증가량 
	static int exercise[]; //운동키트 적용 순서 
	static boolean visited[];
	static int count=0; //조건을 만족하는 경우의 수를 세기 위한 변수 
	
	static void permutation(int depth) { //운동키트의 적용 순서를 구하는 함수 
		if(depth==n) {
			satisfied(exercise);
			return;
		}
		for(int i=1;i<=n;i++) {
			if(visited[i])
				continue;
			exercise[depth]=increase[i];
			visited[i]=true;
			permutation(depth+1);
			visited[i]=false;
		}
	}
	static void satisfied(int exercise[]) { //적용 순서에 따른 조건 만족 여부를 계산하는 함수 
		int weight=500;
		boolean satisfied=true;
		
		for(int i=0;i<exercise.length;i++) {
			weight=(weight-k)+exercise[i];
			
			if(weight<500) {
				satisfied=false;
				break;
			}
		}
		
		if(satisfied) //모든 시점에서 중량이 500보다 작아지지 않은 경우 
			count++; //경우의 수 증가 
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		n=Integer.parseInt(st.nextToken()); 
		k=Integer.parseInt(st.nextToken()); 
		increase=new int[n+1];
		exercise=new int[n];
		visited=new boolean[n+1];
		
		st=new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			increase[i]=Integer.parseInt(st.nextToken());
		}
		
		permutation(0);
		System.out.println(count);
	}

}

 

✏️ 풀이 방법

 

1. 순열을 이용하여 운동 키트 적용 순서를 정한다.

2. 적용 순서에 따른 조건 만족 여부를 계산한다.

=> 조건을 만족할 경우, count를 증가시킨다.

3. 조건을 만족하는 경우의 수(count)를 출력한다. 

 

✏️ 풀이 과정

순열을 이해하기 위해,,

 

나는 아직 재귀호출 함수에 약한 것 같다.

이해가 잘 되지 않아서 혼자 써보면서 이해를 했다.

increase 배열( [1]번째부터 값이 들어있는 ) 값이 { 3, 5, 7 } 일 때 

해당 순열 함수는 3으로 시작하는 모든 경우를 구하고 난 후,

5로 시작하는 , 그리고 마지막으로 7로 시작하는 모든 경우를 구한다.

이를 위해 이 과정에서  visited 배열의 값을 적절하게 true와 false로 설정하여야한다. 

 

✍🏻 느낀점

 

이번 문제를 통해 순열에 대해 알게 되었다.

만약에 이 문제를 순열을 통해 풀지 않았다면 

더 복잡하게 풀지 않았을까 싶다.

 

아직 재귀호출 부분과 visited를 계속 변경하는 부분이

조금 헷갈리지만, 더 공부해서 다른 문제에

잘 적용할 수 있도록 해야겠다.