문제 출처 : 종만북 사탕 공평하게 나눠주기
https://book.algospot.com/candy.html
알고리즘 문제 해결 전략
사탕 나눠주기 문제 예제 문제를 하나 풀면서 점진적인 개선을 어떻게 적용할 수 있나 살펴봅시다. $N(N \le 30)$개의 사탕을 세 명의 어린이에게 가능한 공평하게 나눠 주려고 합니다. 공평함의 기
book.algospot.com
코드설명
30개의 사탕을 세명의 어린이에게 가능한 공평하게 나눠주려고 합니다.
총 4가지 방법으로 접근해보려고 합니다.
1. 사탕을 나눠주는 모든 방법을 만들어보는 완전탐색
2. 각 어린이가 가진 사탕의 총량을 상태 공간으로 하는 너비 우선 탐색 ( 각 상태는 세 어린이가 가진 사탕의 양을 표현하는 세 개의 정수 )
3. 사탕의 최대 무게 차이가 20 임을 이해하여, 시간을 축소시킬 수 있습니다.
4. 세 어린이 중 누가 가장 사탕을 적게 받고, 누가 가장 많이 받는지 중요하지 않습니다.
각 방식을 코드로 짜보았습니다.
1. 완전탐색인 경우
사탕을 3명의 아이에게 나눠주는 모든 경우를 탐색하므로 3^30 이 나옵니다. 3^30은 205조이기에, 205조 / 1억 = 2 2,500,000 (250만초)
250,000,000,000,000 / 1,000,000,000 = 2,500,000 (250만초) = 41,666분 = 694시간이 걸립니다.
여기서 이렇게 오랜 연산 시간이 걸리는 이유는 크게 2가지로 볼 수 있습니다.
첫째, 중복되는 연산이 존재합니다. 즉, 어린이가 어떤 사탕을 받았느냐는 중요하지 않습니다.
세 명의 어린이가 13 42 32 의 사탕의 무게를 가지고 있다고 가정해봅시다.
이때, 13 42 32 나, 42 32 13 이나 결국 우리가 원하는 최대 사탕의 개수 무게와 최소 사탕의 개수 무게는 같습니다.
해당 문제를 사탕 무게의 관점으로 문제를 바꿔겠습니다.
두번쨰, 이미 계산된 부분이 중복될 수 있습니다.
정확히 어떤 중복이 발생할 수 있을지 보겠습니다.
어떤 시점에서 어린이 A, B, C가 각각 5, 10, 10의 사탕 무게를 가지고 있다고 가정해보겠습니다.
이 상태에서 나중에 어떤 다른 경로를 통해 다시 같은 상태(5, 10, 15의 사탕 무게조합)에 도달했다면, 이전에 이미 계산했던 상황과 동일한 상황이므로 다시 계산할 필요가 없습니다. BFS는 선입선출이므로 이미 이전에 해당 상태를 다시 도착했다는 것은 이전에 다른 경로를 통해 이미 그 상태를 방문했으며, 그 시점에서 그 상태로부터 모든 가능한 향후 상태들을 탐색했거나 탐색할 예정이라는 뜻 입니다.
위의 예시를 이해하기 위해서는 BFS와 일반적인 재귀는 모두 시작 노드로부터 가까운 노드부터 차례대로 탐색하는 방식이라는 것을 이해해야 합니다. 이 방식은 해당 레벨을 완전히 탐색한 후에만 다음 레벨로 넘어가는 선입선출의 구조이기에, 순서가 뒤바뀔 가능성은 없습니다.
위의 2가지 원인을 해결하여 시간초과를 해결해보겠습니다.
2. 각 어린이가 가진 사탕의 총량을 상태 공간으로 하는 너비 우선 탐색 ( 각 상태는 세 어린이가 가진 사탕의 양을 표현하는 세 개의 정수 )
읽다보면, 눈에 띄는점이 저자가 특히 이 문제를 "너비 우선 탐색"으로 문제를 분류했다는 점입니다. 그렇기에, "너비우선탐색" 방식으로 코드를 변화시켰습니다.
이런 문제는, 일반적으로 재귀로만 해결해봤었는데 BFS를 활용할경우 책에서 소개하는 여러 최적화 방안을 손쉽게 적용시킬 수 있습니다. 만약 매개변수 안에 각 어린이들의 사탕 무게를 이동시키며 하는 방식으로 한다면 구현하기 어려워 보입니다.
테스트
30개의 사탕이지만, 로직 확인을 위해 사탕이 30개가 아닌경우도 만들었습니다.
입력 예시 1
30
20 20 19 28 1 2 3 2 5 6 7 8 18 2 3 1 18 13 4 8 9 8 3 4 5 2 15 9 12 19결과 예시 1
1
입력 예시 2
3
2 1 0결과 예시 2
2
입력 예시 3
6
20 19 18 9 2 2결과 예시 3
6
코드
1. 완전탐색 코드입니다.
package algorhythm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] candyWeight;
public static int answer = 20 * 30;
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());
candyWeight = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
simulate(0, new int[N]);
System.out.println(answer);
}
public static void simulate(int idx, int[] candyAllocate) {
if(idx == N) {
answer = Math.min(answer, getFairComb(candyAllocate));
return ;
}
candyAllocate[idx] = 1;
simulate(idx + 1, candyAllocate);
candyAllocate[idx] = 2;
simulate(idx + 1, candyAllocate);
candyAllocate[idx] = 3;
simulate(idx + 1, candyAllocate);
}
public static int getFairComb(int[] candyAllocate) {
int minDiff = 0;
int[] child = new int[3];
for(int i=0;i<candyAllocate.length;i++) {
child[candyAllocate[i] - 1] += candyWeight[i];
}
Arrays.sort(child);
minDiff = child[2] - child[0];
return minDiff;
}
}
반복문으로 완전탐색 코드를 조금 줄여봤습니다.
package algorhythm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] candyWeight;
public static int answer = 20 * 30;
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());
candyWeight = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
simulate(0, new int[N]);
System.out.println(answer);
}
public static void simulate(int idx, int[] candyAllocate) {
if(idx == N) {
answer = Math.min(answer, getFairComb(candyAllocate));
return ;
}
for(int i=1; i<=3;i++) {
candyAllocate[idx] = i;
simulate(idx + 1, candyAllocate);
}
}
public static int getFairComb(int[] candyAllocate) {
int minDiff = 0;
int[] child = new int[3];
for(int i=0;i<candyAllocate.length;i++) {
child[candyAllocate[i] - 1] += candyWeight[i];
}
Arrays.sort(child);
minDiff = child[2] - child[0];
return minDiff;
}
}
완전탐색 코드에서 더 단순화 시켜보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M, L;
public static int answer = 0;
public static int[] candyWeight;
public static Child[] child;
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());
candyWeight = new int[N];
child = new Child[3];
for(int i=0;i<3;i++) {
child[i] = new Child();
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
System.out.println(exhaustiveCandyDistribute(0));
}
public static int exhaustiveCandyDistribute(int level) {
if(level == N) {
int biggestWeight = Math.max(child[0].candy, Math.max(child[1].candy, child[2].candy));
int smallestWeight = Math.min(child[0].candy, Math.min(child[1].candy, child[2].candy));
return biggestWeight - smallestWeight;
}
int ret = Integer.MAX_VALUE;
for(int i=0;i<3;i++) {
child[i].candy += candyWeight[level];
ret = Math.min(ret, exhaustiveCandyDistribute(level + 1));
child[i].candy -= candyWeight[level];
}
return ret;
}
}
class Child{
int candy;
public Child() {
}
}
문제의 저자 종만북 저자님이 제안하신, 너비우선탐색 방식입니다.
저는 주로 이런 문제는 위와 같이 재귀코드 완성하는데, 너비우선탐색 방식으로 접근함을 요청하고 있으므로 BFS로 접근해보겠습니다.
하지만, 아래의 코드를 실행해보면, 역시 시간초과가 발생합니다.
package algorhythm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] candyWeight;
public static int answer = 0;
public static int maxWeight = 20;
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());
answer = maxWeight * N + 1;
candyWeight = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
BFS();
System.out.println(answer);
}
public static void BFS() {
Queue<CandyChild> q = new LinkedList<>();
q.offer(new CandyChild(0, new int[] {0,0,0}));
// 사탕의 개수별 조합의 최대 길이는 N.(20 + 1)
// 각자 받을 수 있는 최대 사탕 무개는 600이므로, 배열인덱스를 고려하여 601개의 배열size를 만듭니다.
// 21 * 600*600*600 = 217,081,801 (2억) * 21 = 42억
boolean[][][][] visited = new boolean[N+1][maxWeight * N + 1][maxWeight * N + 1][maxWeight * N + 1];
while(!q.isEmpty()) {
CandyChild childCandyWeight= q.poll();
int level = childCandyWeight.level;
int[] childArr = childCandyWeight.child;
System.out.println("level:" + level+ " childArr[0]:"+childArr[0]+" childArr[1]:"+childArr[1]+" childArr[2]:"+childArr[2]);
//종료합니다.
if(level == N) {
int minValue = Math.min(childArr[0], Math.min(childArr[1], childArr[2]));
int maxValue = Math.max(childArr[0], Math.max(childArr[1], childArr[2]));
answer = Math.min(answer, maxValue - minValue);
continue ;
}
if(visited[level][childArr[0]][childArr[1]][childArr[2]] == true) continue;
visited[level][childArr[0]][childArr[1]][childArr[2]] = true;
for(int child=1; child<= 3;child++) {
int[] newChildArr = childArr.clone();
newChildArr[child - 1] += candyWeight[level];
q.offer(new CandyChild(level + 1, newChildArr));
}
}
}
}
class CandyChild{
int level;
int[] child;
public CandyChild(int level, int[] child) {
this.level = level;
this.child = child;
}
}
제가 처음에 생각을 잘못했었는데요, 저는 VISITED[현재 나눠준 사탕의 인덱스][첫번째 Child가 가지고 있는 사탕의 무게
][두번째 Child가 가지고 있는 사탕의 무게][세번째 Child가 가지고 있는 사탕의 무게] 로 진행했습니다.
여기서 문제가 발생했습니다.
바로 [현재 나눠준 사탕의 인덱스], 즉 VISITED의 첫번째 차원 값은, 필요가 없습니다.
제가 처음에 필요하다고 생각한 이유는, 각 레벨별로 각 어린이가 가진 상태 총량을 저장해두어야만 구분이 된다고 생각했습니다만, 시간초과가 나고서 다시 생각해보았습니다.
사실상 만약 VISITED[][][] 에서 이미 해당 부분을 검사했다면, 이후에 검사하는 경우와 중복됨을 알 수 있습니다.
첫번째 차원(level : 사탕을 몇개 나눠주었는지)을 제거하여, 중복해서 검사하는 부분을 모두 제거해주겠습니다.
package algorhythm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] candyWeight;
public static int answer = 0;
public static int maxWeight = 20;
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());
answer = maxWeight * N + 1;
candyWeight = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
BFS();
System.out.println(answer);
}
public static void BFS() {
Queue<CandyChild> q = new LinkedList<>();
q.offer(new CandyChild(0, new int[] {0,0,0}));
// 사탕의 개수별 조합의 최대 길이는 N.(20 + 1)
// 각자 받을 수 있는 최대 사탕 무개는 600이므로, 배열인덱스를 고려하여 601개의 배열size를 만듭니다.
// 600*600*600 = 217,081,801 (2억)
boolean[][][] visited = new boolean[maxWeight * N + 1][maxWeight * N + 1][maxWeight * N + 1];
while(!q.isEmpty()) {
CandyChild childCandyWeight= q.poll();
int level = childCandyWeight.level;
int[] childArr = childCandyWeight.child;
// System.out.println("level:" + level+ " childArr[0]:"+childArr[0]+" childArr[1]:"+childArr[1]+" childArr[2]:"+childArr[2]);
//종료합니다.
if(level == N) {
int minValue = Math.min(childArr[0], Math.min(childArr[1], childArr[2]));
int maxValue = Math.max(childArr[0], Math.max(childArr[1], childArr[2]));
answer = Math.min(answer, maxValue - minValue);
continue ;
}
if(visited[childArr[0]][childArr[1]][childArr[2]] == true) continue;
visited[childArr[0]][childArr[1]][childArr[2]] = true;
for(int child=1; child<= 3;child++) {
int[] newChildArr = childArr.clone();
newChildArr[child - 1] += candyWeight[level];
q.offer(new CandyChild(level + 1, newChildArr));
}
}
}
}
class CandyChild{
int level;
int[] child;
public CandyChild(int level, int[] child) {
this.level = level;
this.child = child;
}
}
BFS 코드.(시간통과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M, L;
public static int answer = 0;
public static int[] candyWeight;
public static Child[] child;
public static int maxWeight = 20;
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());
candyWeight = new int[N];
child = new Child[3];
for(int i=0;i<3;i++) {
child[i] = new Child();
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
System.out.println(BFSCandyDistribute());
}
public static int BFSCandyDistribute() {
Queue<Child> q = new LinkedList<>();
q.offer(new Child());
int ret = maxWeight * N + 1;
boolean[][][] visited = new boolean[maxWeight * N + 1][maxWeight * N + 1][maxWeight * N + 1];
while(!q.isEmpty()) {
Child child = q.poll();
int level = child.level;
int[] childCandyWeight = child.childCandyWeight;
if(level == N) {
int biggestWeight = Math.max(childCandyWeight[0], Math.max(childCandyWeight[1], childCandyWeight[2]));
int smallestWeight = Math.min(childCandyWeight[0], Math.min(childCandyWeight[1], childCandyWeight[2]));
ret = Math.min(ret, biggestWeight - smallestWeight);
continue;
}
if(visited[childCandyWeight[0]][childCandyWeight[1]][childCandyWeight[2]] == true) {
continue;
}
visited[childCandyWeight[0]][childCandyWeight[1]][childCandyWeight[2]] = true;
for(int i=0; i<3; i++) {
Child nChild = new Child();
nChild.level = level + 1;
int[] nChildCandyWeight = new int[3];
for(int j=0;j<3;j++) {
nChildCandyWeight[j] = childCandyWeight[j];
}
nChildCandyWeight[i] += candyWeight[level];
nChild.childCandyWeight = nChildCandyWeight;
q.offer(nChild);
}
}
return ret;
}
}
class Child{
int level; //level을 사용하여 BFSCandyDistribute에서 q의 Size만큼 사탕의 현재 level을 확인할 필요가 없다. 훨씬 로직이 간단해지고 간편하다.
int[] childCandyWeight = new int[3];
public Child() {
}
}
사탕을 가장 많이받은 어린이와 가장 적게 받은 어린이의 차이가 20 이상이었다고 가정해본 문제입니다.
사탕의 최대 무게는 20이므로, 이때 사탕을 가장 많이 받은 어린이가 가장 적게 받은 어린이보다 20 초과로 많다면, 해당 방식은 어처피 의미가 없습니다.
이유는, 반드시 더 나은 방식이 존재하기 때문입니다.
그렇기에, 최대 무게를 221 로 설정하여, 한 어린이가 가지고 있는 사탕이 220을 초과하는 경우는 연산을 진행시키지 않습니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] candyWeight;
public static int answer = 0;
public static int maxWeight = 20;
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());
long startTime = System.currentTimeMillis();
answer = maxWeight * N + 1;
candyWeight = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
BFS();
System.out.println(answer);
long endTime = System.currentTimeMillis();
System.out.println("Time:" + (endTime - startTime));
}
public static void BFS() {
Queue<CandyChild> q = new LinkedList<>();
q.offer(new CandyChild(0, new int[] {0,0,0}));
boolean[][][] visited = new boolean[ (maxWeight * N / 3) + 21][(maxWeight * N / 3) + 21][(maxWeight * N / 3) + 21];
while(!q.isEmpty()) {
CandyChild childCandyWeight= q.poll();
int level = childCandyWeight.level;
int[] childArr = childCandyWeight.child;
int minValue = Math.min(childArr[0], Math.min(childArr[1], childArr[2]));
int maxValue = Math.max(childArr[0], Math.max(childArr[1], childArr[2]));
if(level == N) {
answer = Math.min(answer, maxValue - minValue);
continue ;
}
if(maxValue >= (maxWeight * N / 3) + 20) continue;
if(visited[childArr[0]][childArr[1]][childArr[2]] == true) continue;
visited[childArr[0]][childArr[1]][childArr[2]] = true;
for(int child=1; child<= 3;child++) {
int[] newChildArr = childArr.clone();
newChildArr[child - 1] += candyWeight[level];
q.offer(new CandyChild(level + 1, newChildArr));
}
}
}
}
class CandyChild{
int level;
int[] child;
public CandyChild(int level, int[] child) {
this.level = level;
this.child = child;
}
}
위의 BFS + 220 이상의 무게일경우 검사안하는 코드와 유사한 코드입니다.
하지만, 실제로는 maxWeight와 minWeight를 매번 검사해야하므로 속도가 비교적 느릴 것이라 생각됩니다.
3^30 개의 계산이 필요하기 떄문입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M, L;
public static int answer = 0;
public static int[] candyWeight;
public static Child[] child;
public static int maxWeight = 20;
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());
candyWeight = new int[N];
child = new Child[3];
for(int i=0;i<3;i++) {
child[i] = new Child();
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
System.out.println(BFSCandyDistribute());
}
public static int BFSCandyDistribute() {
Queue<Child> q = new LinkedList<>();
q.offer(new Child());
int ret = maxWeight * N + 1;
boolean[][][] visited = new boolean[maxWeight * N + 1][maxWeight * N + 1][maxWeight * N + 1];
while(!q.isEmpty()) {
Child child = q.poll();
int level = child.level;
int[] childCandyWeight = child.childCandyWeight;
int biggestWeight = Math.max(childCandyWeight[0], Math.max(childCandyWeight[1], childCandyWeight[2]));
int smallestWeight = Math.min(childCandyWeight[0], Math.min(childCandyWeight[1], childCandyWeight[2]));
if(level == N) {
ret = Math.min(ret, biggestWeight - smallestWeight);
continue;
}
if(biggestWeight >= (((maxWeight * N) / 3) + maxWeight)) continue;
if(visited[childCandyWeight[0]][childCandyWeight[1]][childCandyWeight[2]] == true) {
continue;
}
visited[childCandyWeight[0]][childCandyWeight[1]][childCandyWeight[2]] = true;
for(int i=0; i<3; i++) {
Child nChild = new Child();
nChild.level = level + 1;
int[] nChildCandyWeight = new int[3];
for(int j=0;j<3;j++) {
nChildCandyWeight[j] = childCandyWeight[j];
}
nChildCandyWeight[i] += candyWeight[level];
nChild.childCandyWeight = nChildCandyWeight;
q.offer(nChild);
}
}
return ret;
}
}
class Child{
int level; //level을 사용하여 BFSCandyDistribute에서 q의 Size만큼 사탕의 현재 level을 확인할 필요가 없다. 훨씬 로직이 간단해지고 간편하다.
int[] childCandyWeight = new int[3];
public Child() {
}
}
마지막 최적화 방법입니다. 사탕을 누가 많이 받든, 적게 받든 우리가 원하는 것은 최소 사탕의 차이이기 때문에, 오름차순 정렬하여 순서를 상관쓰지 않습니다. 그럴경우 3! -> 3 * 2 * 1 = 6가지 경우 중에서 1가지 경우만 고려하면 되게 됩니다.
즉, Visited[][][] 에서 항상 정렬된 값만 검색하므로 중복연산이 매우 줄어듭니다.
예시로는 (180, 190, 200) 이건 (190, 180, 200)이건 둘다 답은 20입니다. 이떄, 두개를 모두 같은 건으로 볼 수 있으므로 이전의 연산들 또한 다 삭제되어 애초에 이 Level까지 오는 경우를 줄입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] candyWeight;
public static int answer = 0;
public static int maxWeight = 20;
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());
long startTime = System.currentTimeMillis();
answer = maxWeight * N + 1;
candyWeight = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
candyWeight[i] = Integer.parseInt(st.nextToken());
}
BFS();
System.out.println(answer);
long endTime = System.currentTimeMillis();
System.out.println("Time:" + (endTime - startTime));
}
public static void BFS() {
Queue<CandyChild> q = new LinkedList<>();
q.offer(new CandyChild(0, new int[] {0,0,0}));
boolean[][][] visited = new boolean[ (maxWeight * N / 3) + 21][(maxWeight * N / 3) + 21][(maxWeight * N / 3) + 21];
while(!q.isEmpty()) {
CandyChild childCandyWeight= q.poll();
int level = childCandyWeight.level;
int[] childArr = childCandyWeight.child;
Arrays.sort(childArr);
int minValue = Math.min(childArr[0], Math.min(childArr[1], childArr[2]));
int maxValue = Math.max(childArr[0], Math.max(childArr[1], childArr[2]));
if(level == N) {
answer = Math.min(answer, maxValue - minValue);
continue ;
}
if(maxValue > (maxWeight * N / 3) + 20) continue;
if(visited[childArr[0]][childArr[1]][childArr[2]] == true) continue;
visited[childArr[0]][childArr[1]][childArr[2]] = true;
for(int child=1; child<= 3;child++) {
int[] newChildArr = childArr.clone();
newChildArr[child - 1] += candyWeight[level];
q.offer(new CandyChild(level + 1, newChildArr));
}
}
}
}
class CandyChild{
int level;
int[] child;
public CandyChild(int level, int[] child) {
this.level = level;
this.child = child;
}
}
'알고리즘 > 알고리즘 문제해결 전략' 카테고리의 다른 글
| [종만북] 성형 전 사진 찾기 - 이진탐색(Binary Search) JAVA (0) | 2024.05.15 |
|---|---|
| [종만북] 다이어트 현황 파악 : 이동 평균 계산하기 - 슬라이딩 윈도우(Sliding Window) + 누적합(Prefix Sum) JAVA (0) | 2024.05.15 |
| [종만북] 신문기사의 오류 확인하기 ( 400m 달리기 ) - JAVA (0) | 2024.05.12 |
| [종만북] 격자 위에서 기존에 있던 점까지의 거리의 합을 최소화하는 위치 찾기 - JAVA (0) | 2024.05.12 |
| [알고스팟] FESTIVAL 록 페스티벌 - 구현(Implementation) + 누적합(PrefixSum) JAVA (0) | 2024.05.08 |