SW_EXPERT_3234_준환이의 양팔저울

문제 링크는 아래 있습니다. 

무단 복제가 허용되지 않기 때문에 링크로 걸어둔 점 양해바랍니다. 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE

이 문제는 순열로 풀어도 되고 탐색으로도 되는데, 저는 탐색으로 풀었습니다.

탐색할 때 중요한 것은 첫 번째 숫자를 집어 넣을 당시에 left에 먼저 넣어두고 다시 방문하지 않도록 체크하는 것입니다.

가령, 예제에서 1 2 4 를 다루고 있으니 가져와서 설명하자면,

LEFT 

 1    2     4

RIGHT

이런 식으로 LEFT에 먼저 값을 넣어주고 생각해야지, RIGHT에 먼저 넣게되면 문제가 발생합니다.

또한, LEFT에 값을 추가할 때 1을 넣은 후에 2를 넣어야하는데, 방문했다고 체크하지 않는다면, 

즉, 1의 값을 갖는 노드를 방문했다고 체크하지 않는다면, 1  1  1  ...... 이렇게 값이 들어갈 것입니다.

따라서 방문 여부를 체크해주고, LEFT에 값이 다 채워진 뒤, RIGHT와 대소비교하면서 RIGHT를 늘리는 재귀적 호출을 

하면 되는 겁니다.

재귀 호출시, 조건은 문제에 나와있는대로, LEFT의 총합이 RIGHT의 총합보다 항상 커야한다고 두면 되고, 조건 이후에는 
RIGHT 값을 증가시키면서 재귀 호출하면 됩니다.

---

앞서 말한 내용의 코드는 다음과 같습니다.

---

for (int i = 0; i < N; i++) {

// 값을 left부터 먼저 넣고 돌리기

if (visited[i] == 1)

continue;

visited[i] = 1;

calc(inx + 1, left + scale[i], right, N);

if (left - (scale[i] + right) >= 0)

calc(inx + 1, left, right + scale[i], N);

visited[i] = 0;

}

---

기저 조건으로 함수가 끝날 경우, 호출 전 상태로 다시 돌아오는데, 그 때에는 방문했던 것을 하지 않았다고 

다시 체크해줘서 다른 경우의 수를 체크할 수 있도록 합니다.

기저 조건은 원래는 한 가지입니다.

값을 담고 있는 배열의 인덱스가 배열 전체의 크기를 넘어설 경우 리턴하는 것입니다.

하지만 문제에서 최대 탐색의 범위는 N! * 2^N이기 때문에 해당 범위까지 들어가서 체크한다면, 

타임아웃이 뜰 것입니다.

따라서 타임아웃을 줄이기 위해서는, 탐색 범위가 최대치를 달성할 때, 즉, 배열 요소의 총합까지 

체크할 경우 N! * 2^N을 카운트에 더해주면 됩니다.

가령, 1~9까지의 합이라고 할 때, 처음 범위 설정 시, LEFT에 배열 요소 값들을 계속해서 더해줄 것이고, 

배열 요소의 총합(1~9까지 : 45)과 비교하여 최대 범위에 도달한 지를 체크합니다.

즉, LEFT가 36일 때 전체합 (45) - 9가 36과 같아지므로, 최대 범위가 될 것이며, 당시의 카운트는 N! * 2^N을 더해주면 됩니다.

단, 주의해야할 점은 LEFT가 커질 경우도 생길 수 있으므로 LEFT >= SUM - LEFT로 기저조건을 줘야합니다.

<전체 코드>

---

import java.util.Scanner;

public class 준환이의_양팔저울2 {

private static int[] scale;

private static Scanner scanner;

private static int count = 0;

private static int visited[];

        private static int exponential[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };

        private static int factorial[] = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

        private static int sum = 0;

    

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int testCase = scanner.nextInt();

int index = 0;

while (testCase-- > 0) {

int N = scanner.nextInt();

scale = new int[N];

visited = new int[N];

for (int i = 0; i < N; i++) {

scale[i] = scanner.nextInt();

sum += scale[i];

}

calc(0, 0, 0, N);

System.out.println("#" + (++index) + " " + count);

sum = 0;

count = 0;

}

}

// visited 배열은 방문한 곳을 더이상 방문하지 않도록 , 즉 중복으로 left에 1 1 1 이렇게 안더해지도록 하는 역할

private static void calc(int inx, int left, int right, int N) {

if (inx >= N) {

count += 1;

return;

}

// 최대 카운트수는 2^n * n!이므로 

// 아래와 같이 count에 추가해줍니다.

// 단, left에 값을 계속해서 추가하고 있고, sum은 앞서 요소들의 전체 값이므로 

// left >= sum - left의 조건을 만족하기 위해서는 결국 마지막까지는 돌아야 한다는 사실을 알 수 있다.

// 가령 9를 예를 들면, 합은 45이며, left가 1~8까지의 합을 더했을 때 남은 9와 

// sum - left의 결과인 9와 상충되므로 아래 조건을 만족한다.

// 끝단까지 갔을 때 count를 하나씩 증가시키지 않고 바로 값을 추가하고 리턴하여 시간을 줄이는 것이다.

if(left >= sum - left) {

count += exponential[N-inx] * factorial[N-inx];

return;

}

for (int i = 0; i < N; i++) {

// 값을 left부터 먼저 넣고 돌리기

if (visited[i] == 1)

continue;

visited[i] = 1;

calc(inx + 1, left + scale[i], right, N);

if (left - (scale[i] + right) >= 0)

calc(inx + 1, left, right + scale[i], N);

visited[i] = 0;

}

}

}

---

감사합니다.