백준 18429번 근손실 <S3> - 브루트 포스

 

요즘은 문제 지문이 긴걸 위주로 풀려고하게 된다.

아무래도 코테 문제는 지문이 길지 않을까..? 하는 혼자 생각때문에 호호

먼저 근손실은 마음이 아프다,, 운동 못한지가 오래되서인지 문제 제목보고 홀린듯 풀게 되었다.

지문을 읽게되면 3대 500에서 (ㄷㄷ) 매일 매일 K만큼 중량이 줄게된다. 다만 키트가 있어서 키트를 꽂으면 중량이 즉시 증가하는데 이 대학원생은 욕심쟁이라 늘 500이상을 유지하고 싶어한다. 어떤 시점에서 봐도 500보다 작지 않도록 키트 순서를 정해주면 된다. 이 순서 경우의 수를 출력하면 되는 문제다.

 

막상 지문만 길지 짧게 표현할 수 있는 문제였다. 500에서 K * N 만큼 감소하되 키트를 사용하여 500 언더로 안떨어지게 하면 되는 문제다..

 

모든 경우의 수를 출력하면 되기에 모든 경우의 수를 따져주었다.

재귀함수를 사용했고, 재귀 반복간에 변동되는 값이 없도록 신경써주면 브루트 포스 알고리즘 끝이다.

 

*브루트 포스 : 무식하게 모든 경우의 수를 따지는 방법 과거는 시간과 자원이 많이 들었다면 요즘은 컴퓨터라.. ㅎㅎ

 과거 세계지도의 모든 나라를 4가지 색으로 표현이 가능하다인 '4색 정리' 같은 경우도 증명에 이 알고리즘이 사용되었던걸로 기억한다.

 

 

import java.util.*;
 
public class Main {
    static int answer = 0;
    static int N;
    static int K;
    static int[] kit;
    static boolean[] used;
 
    public static void steroid(int sum, int day) {
        if (day == N) {
            answer++;
            return;
        }
 
        for (int i = 0; i < N; i++) {
            if (!used[i] && (sum + kit[i] - K) >= 0) {
                used[i] = true;
                steroid(sum + kit[i] - K, day + 1);
                used[i] = false; // 다시 원래대로 바꿔주기. 필수*
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        // Input
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 1 <= N <= 8
        K = sc.nextInt(); // 1 <= K <= 50
        kit = new int[N];
        used = new boolean[N];
        for (int i = 0; i < N; i++) {
            kit[i] = sc.nextInt();
        }
 
        // Main logic
        steroid(0, 0);
 
        // Output
        System.out.println(answer);
    }
}
 

 

if (!used[i] && (sum + kit[i] - K) >= 0) 조건으로 감소량 K 랑 키트 증가량kit[i]랑 비교하여 판단한다.

만약 만족하지 못하면 종료.

만족하는경우

used 배열에서 true 로 바꾸고, 다시 다음 값을 넣어 함수를 실행한다. 그런 후 꼭 used 배열을 false로 해줘여 한다.

반복한 횟수가 N이되면 -> 즉 8일차까지 모두 500이상이라면 answe++ 한다.