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

난이도

실버 3

문제

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

풀이

백트래킹 사용

1) 틀린 코드 풀이

ex) n=3, k=4, 운동키트번호(중량증가량) 1(3),2(7),3(5)
1. 키트를 사용할 수 있는 경우의 수를 구하기 위해 백트래킹을 수행
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
총 6가지 방법을 키트를 사용할 수 있음

2. 백트래킹을 다 돌았을 때(idx == n), n일 간의 중량 계산하고 날마다 중량이 500이상일 때만 경우의 수를 증가
   1,2,3 -> 499,502,503 (x)
   1,3,2 -> 499,500,503 (x)
   2,1,3 -> 503,504,505 (o)
   2,3,1 -> 503,504,503 (o)
   3,1,2 -> 501,500,503 (o)
   3,2,1 -> 501,502,501 (o)

이러한 방법으로 문제를 해결하였는데 정답을 제출하니 25%에서 틀렸습니다가 발생했다. 일일이 모든 경우의 수를 구하고 그 중 맞는 경우를 찾아야하다보니 비효율적인 코드라는 생각이 들었다.
그래서 백트래킹을 수행하며 sum을 구하는 방법으로 수정했다.

2) 정답 풀이

    static void back(int sum, int idx) {
        if (idx == n) {
            ans++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visit[i] && (sum + arr[i] - k) >= 500) {
                visit[i] = true;
                back(sum + arr[i] - k, idx + 1);
                visit[i] = false;
            }
        }
    }

1. 백트래킹을 수행할 때, 매개변수로 sum과 idx를 넣는다.
2. 방문여부와 sum의 값이 500 이상인지를 판단하여 백트래킹을 수행한다.
3. 종료조건) idx와 n이 같을 때, 경우의 수를 증가시키고 리턴한다.

코드

1) 틀린 코드(25%에서 틀렸습니다)

package 백트래킹;

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

public class BOJ18429 {
    static int n, k;
    static int[] arr;
    static boolean[] visit;
    static int ans;
    static int[] tmp;
    static int sum;

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

        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

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

        visit = new boolean[n];
        tmp = new int[n];
        ans = 0;
        sum = 500;
        back(0);
        System.out.println(ans);
    }

    static void back(int idx) {
        if (idx == n) {
            if (checkStatus(tmp)) {
                ans++;
            }
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                tmp[idx] = arr[i];
                back(idx + 1);
                visit[i] = false;
            }
        }
    }

    static boolean checkStatus(int[] tmp) { // 계속 500이상을 유지한다면
        for (int val : tmp) {
            sum += val - k;
            if (sum < 500) {
                return false;
            }
        }
        return true;
    }


}

2) 정답코드

package 백트래킹;

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

public class BOJ18429 {
    static int n, k;
    static int[] arr;
    static boolean[] visit;
    static int ans;

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

        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

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

        visit = new boolean[n];
        ans = 0;
        back(500, 0);
        System.out.println(ans);
    }

    static void back(int sum, int idx) {
        if (idx == n) {
            ans++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visit[i] && (sum + arr[i] - k) >= 500) {
                visit[i] = true;
                back(sum + arr[i] - k, idx + 1);
                visit[i] = false;
            }
        }
    }

}