[BOJ-Silver3] 18429번 근손실

💡 첫번째 풀이

✔️ 조합 알고리즘

• n의 범위가 8 이하로 작아서 조합 알고리즘으로 운동 키트 사용 순서를 뽑아내서 중량 계산
• 계산 중에 500 이상만 cnt++
• cnt가 n이랑 같으면 모두 중량 500 이상이므로 result +1

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

public class Main {
	static int[] weight;
	static boolean[] visited;
	static int n, k, result = 0;

	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());

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

		visited = new boolean[n];
		int[] output = new int[n];
		permutation(output, 0);
		System.out.println(result);
	}
    
	public static void permutation(int[] output, int depth){
		// 운동 키트 순서를 다 골랐으면 중량 계산하기
        // 계산 중에 500 미만이 되면 break
        // 500 이상만 골라서 cnt++
        // cnt가 n이면 n개가 다 중량 500 이상이므로 result++
        if (depth == n){ 
			int sum = 500;
			int cnt = 0;
			for(int i = 0; i<n; i++){
				sum = sum + weight[output[i]] - k;
				if (sum < 500)
					break;
				cnt++;
			}
			if (cnt == n) result++;
			return;
		}

		for(int i = 0; i<n; i++){
			if (!visited[i]){
				visited[i] = true;
				output[depth] = i;
				permutation(output, depth+1);
				visited[i] = false;
			}
		}
	}
}

💡 두번째 풀이

✔️ 백트래킹

• 위 조합 풀이로도 맞았지만 뭔가 복잡해서 다시 풀기
• output으로 조합으로 키트 순서를 하나씩 보지 않고 방문하지 않은 순서는 즉시 바로 중량 계산하기
• 계산해서 500이 넘으면 다음 백트래킹 수행
• 조합 알고리즘을 무작정 외우다보니 이런 풀이가 잘 생각이 안남 ..

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

public class Main {
	static int[] weight;
	static boolean[] visited;
	static int n, k, result = 0;

	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());

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

		visited = new boolean[n];
		backtrack(500, 0);
		System.out.println(result);
	}
    
	public static void backtrack(int currWeight, int depth){
    	// depth가 n에 도달했으면 result +1
		if (depth == n){
			result ++;
			return;
		}

		for(int i = 0; i<n; i++){
			if (!visited[i]){
            	// weight 계산 후 500이 넘으면 다음 백트래킹 수행
				int nextWeight = currWeight + weight[i] - k;
				if (nextWeight >= 500){
					visited[i] = true;
					backtrack(nextWeight, depth+1);
					visited[i] = false;
				}
			}
		}
	}
}