[코딩 테스트] 근손실 (feat. 백트래킹)

문제 출처

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

 

문제 풀이 생각 

1. 모든 경우의 수를 구한다음에 하나씩 확인해본다

2. 백트래킹으로 중간에 안되는 경우(500 이하일 경우) 탐색하지 않는다.

 

나는 2번과정으로 푸는 것이 맞을 것 같아서 예시를 보고서 그래프를 한번 그려보았다.

 

예시는 다음과 같다.

 

 

총 3개의 경우를 그려보겠다.

 

selected배열을 만들어서 해당 키트 번호를 이미 골랐는지 관리를 해주도록 하였다. 그것을 그림으로 (F,F,T)또는 (F,F,F)등..으로 나타내겠다

 

먼저 처음 1번 키트를 적용할 때

 

다음과 같이 1번을 적용하면 500보다 작아지게 되므로, 백트래킹이 수행되게 된다.

 

2번 키트를 먼저 적용할 때

 

 

500을 만족하니 재귀 호출로 다시 불러준다.

 

그 다음 506이 500보다 크니 재귀 호출로 불러오고, 재귀 호출 종료 조건(모든 숫자를 방문하였을 경우)을 만족해서 return한다

 

 

그 다음 계속해서 재귀호출이 실행되면 다음과 같은 그래프 최종본이 완성되게 된다.

 

 

그래서 총 가능한 운동 가지 수는 총 4가지가 나오게 된다.

 

여기서 핵심은 지금 1번은 백트리킹 한 부분으로 볼 수 있다.

물론 지금은 운동키트가 3개라서 효율적으로 보이지 않을지라도 운동키트가 커진다면, 전체를 탐색하지 않아도 되는 좋은 효율성을 보여줄 것이다.

 

코드

 

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

public class Main {

    private static int answer = 0;
    private static int[] w;
    private static int k;
    private static int n;
    private static boolean[] selected;


    public static void main(String[] args)throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

        String[] NK = br.readLine().split(" ");
        n = Integer.parseInt(NK[0]);    //N일
        k = Integer.parseInt(NK[1]);    //K만큼 감소
        String[] weight = br.readLine().split(" ");
        w = Arrays.stream(weight).mapToInt(Integer::parseInt).toArray();  //각 운동당 얻는 근육량

        selected = new boolean[n];

        backTracking(500);

        System.out.println(answer);
    }

    private static boolean isFinished(boolean[] selected){
        for(int i = 0 ; i<selected.length;i++){
            if(!selected[i]) return false;
        }
        return true;
    }





    private static void backTracking(int muscle){
        if(isFinished(selected)){
            answer++;
            return;
        }

        for(int i= 0 ;i<n;i++){
            if(selected[i]){
               continue;
            }
            if(muscle-k+w[i]>=500){
                selected[i]=true;
                backTracking(muscle-k+w[i]);
                selected[i]=false;
            }
        }
    }

}