[백준/JAVA] 18429번: 근손실

📖 문제

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

 

 

 

💡  풀이 방식

• DFS (조합)

백트래킹으로 운동 키트 번호를 뽑는다. (중복 X)

뽑은 운동 키트를 순서대로 돌면서, 중량이 모두 500 이상인 경우만 정답 +1을 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,K,answer;
    static int[] arr;
    static boolean[] chk;
    static List<Integer> list = new ArrayList<>(); // 뽑은 운동 키트의 중량 증가량 저장 리스트
    
    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());
        
        arr = new int[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        chk = new boolean[N];
        dfs(0, 0);
        
        System.out.println(answer);
    }
    
    private static void dfs(int idx, int depth) {
        if(depth == N) {
            int weight = 500;
            
            for(int i : list) {
                weight = weight - K + i;
                
                if(weight < 500) // 중량이 500 미만이라면 종료
                    return;
            }
            
            answer++; // 운동 기간 동안 항상 중량이 500 이상이면 경우의 수 +1               
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            if(!chk[i]) {
                chk[i] = true;
                list.add(arr[i]);
                dfs(i + 1, depth + 1);
                chk[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

백트래킹 함수 변수에 중량을 들고 다니면서 계산하셨다.

[백준] 18429번 근손실 - Java, 자바

 

 

1회독	2회독	3회독	4회독	5회독
V