백준 18429 근손실

백준 18429 근손실

백준 18429 근손실

구현 전 생각

이 문제는 키트 번호를 순열을 이용하여 키트를 완전 탐색하는 방법으로 해결할것이다.
거기에 중량이 500밑으로 내려가는 경우를 리턴하여 백프로파게이션으로 구현 하면 될것같다.
최대 일수가 N이고 키트 갯수가 50이라 시간 제한안에 해결 가능할것 같다.

아쉬운점

순열을 만들때 바로 계산해주면 필요 없는 순열을 만들지 않아서 더 빠르게 동작 할것 같다!
->구현 결과 : 더 빠르지는 않았지만 훨씬더 간단한 코드가 완성 되었다. 아마도 더 빠르게 작성하려고 하면 재귀를 사용하지 않고 직접적으로 포문을 사용할것

코드(간단한 버전)

package com.study26;

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

public class backjoon_18429_근손실 {
	static int N,K;
	static int[] kit;
	static int[] numbers;
	static boolean isSelected[];

	static int cntNum=0;;
	public static void permutation(int cnt,int weight) {
		//순열이 키트의 개수 만큼 다 만들어진 경우
		if(weight<0) return;
		if(cnt == N) {
			cntNum++;
			return;
		}
		for (int i = 0; i < N; i++) {
			if(isSelected[i]) continue;
			isSelected[i] = true;
			
			permutation(cnt+1,weight+kit[i]-K);
			isSelected[i] = false;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		kit = new int[N];
		numbers= new int[N];
		isSelected= new boolean[N];
		
		st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++) {
			kit[i]= Integer.parseInt(st.nextToken());
		}
		//순열 사용
		permutation(0,0);
		System.out.println(cntNum);
	}
}

코드(pass)

package com.study26;

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

public class backjoon_18429_근손실 {
	static int N,K;
	static int[] kit;
	static int[] numbers;
	static boolean isSelected[];

	static int cntNum;
	public static void permutation(int cnt) {
		//순열이 키트의 개수 만큼 다 만들어진 경우
		if(cnt == N) {
			sum();
			return;
		}
		for (int i = 0; i < N; i++) {
			if(isSelected[i]) continue;
			numbers[cnt]=i;
			isSelected[i] = true;
			permutation(cnt+1);
			isSelected[i] = false;
		}
	}
	public static void sum() {
		int temp=0;
		for (int i = 0; i < N; i++) {
			//중량에 키트를 먼저 더한후 오늘 빠져나가는 중량을 빼준다 
			temp=temp+kit[numbers[i]];
			temp-=K;
			//만약 음수가 나오면 500밑으로 떨어진 경우기 때문에 리턴
			if(temp<0) return;
		}
		//키트가 음수가 되지 않으면 가능한 것임으로 카운트를 +1
		cntNum++;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		kit = new int[N];
		numbers= new int[N];
		isSelected= new boolean[N];
		
		st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++) {
			kit[i]= Integer.parseInt(st.nextToken());
		}
		//순열 사용
		permutation(0);
		System.out.println(cntNum);
	}
}