[アルゴリズム]バックアップ-ブラックジャック
11344 ワード
白駿-黒ジャック
説明する
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class baekjoon_2798 {
static int[] arr;
static int answer = Integer.MAX_VALUE;
static int M;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
M = Integer.parseInt(inputs[1]);
arr = new int[N];
inputs = br.readLine().split(" ");
for (int i = 0; i < inputs.length; i++) {
arr[i] = Integer.parseInt(inputs[i]);
}
backTracking(0, 0, 0);
System.out.println(answer);
}
private static void backTracking(int curIndex, int curSum, int count) {
if ((curIndex >= N && count < 3) || curSum > M) {
return;
}
if (count == 3) {
if (Math.abs(answer - M) > Math.abs(curSum - M)) {
answer = curSum;
}
return;
}
backTracking(curIndex+1, curSum + arr[curIndex], count + 1);
backTracking(curIndex+1, curSum, count);
}
}
バイナリを使用するように、インデックスの数をとり、取らない場合に分けて遡及します.Reference
この問題について([アルゴリズム]バックアップ-ブラックジャック), 我々は、より多くの情報をここで見つけました https://velog.io/@injoon2019/알고리즘-백준-블랙잭テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol