https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw
주어진 조건에 맞게 양팔저울에 추를 올리는 경우의 수를 구하는 문제입니다.
Java의 경우에는 모든 경우에 대해 순열을 구하고 그 순열이 조건에 적합한지 검증을 하면서 가지치기를 해도 주어진 실행시간 안에 통과가 되지만, 조금 더 효율적으로 코드를 짤 수 있는 방법들이 있어 3가지를 전부 소개해드리겠습니다.
우선 기본적으로 모든 순열을 만들고, 이후 조건에 맞는 경우를 찾는 코드입니다.
시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고 2^(N-현재 단계)만큼 더해주었습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class q3234_SWEA_준환이의양팔저울 {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, answer, total;
static Integer[] gram;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
answer = 0;
total = 0;
gram = new Integer[N];
st = new StringTokenizer(br.readLine());
for (int n = 0; n < N; n++) {
gram[n] = Integer.parseInt(st.nextToken());
total += gram[n];
}
total /= 2;
makePermutation(0, new int[N], new boolean[N]);
sb.append("#").append(tc).append(" ").append(answer).append("\n");
}
System.out.println(sb);
}
static void makePermutation(int count, int[] choosed, boolean[] visited) {
if (count == N) {
check(1, choosed, choosed[0], 0);
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
choosed[count] = gram[i];
makePermutation(count + 1, choosed, visited);
visited[i] = false;
}
}
}
static void check(int count, int[] choosed, int left, int right) {
if (count == N) {
answer++;
return;
}
if (total < left) {
int num = 1;
for (int i = 0; i < N - count; i++) {
num *= 2;
}
answer += num;
return;
}
if (left >= right + choosed[count]) {
check(count + 1, choosed, left, right + choosed[count]);
}
check(count + 1, choosed, left + choosed[count], right);
}
}
두 번째론 모든 순열을 만들지 않고, 순열을 만드는 과정 안에 조건에 따른 검증을 넣어서 가지치기한 코드입니다.
마찬가지로 시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고, (N-현재 단계)! * 2^(N-현재 단계)만큼 더해주었습니다.
순열이 다 만들어지지 않았기 때문에 경우의 수를 계산할 때 남은 추의 개수 팩토리얼까지 곱해주어야 합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class q3234_SWEA_준환이의양팔저울Re {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, answer, total;
static Integer[] gram;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
answer = 0;
total = 0;
gram = new Integer[N];
st = new StringTokenizer(br.readLine());
for (int n = 0; n < N; n++) {
gram[n] = Integer.parseInt(st.nextToken());
total += gram[n];
}
total /= 2;
makePermutation(0, new boolean[N], 0, 0);
sb.append("#").append(tc).append(" ").append(answer).append("\n");
}
System.out.println(sb);
}
static void makePermutation(int count, boolean[] visited, int left, int right) {
// System.out.println(count + "선택됨," + left + " : " + right);
if (count == N) {
answer++;
return;
}
if (total < left) {
int num = 1;
for (int i = 1; i <= N - count; i++) {
num *= 2;
num *= i;
}
answer += num;
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
makePermutation(count + 1, visited, left + gram[i], right);
if (right + gram[i] <= left) {
makePermutation(count + 1, visited, left, right + gram[i]);
}
visited[i] = false;
}
}
}
}
세 번째로 메모이제이션을 활용해서 이미 탐색한 경우를 스킵한 코드입니다.
어떤 방법으로든 추의 위치 배정이 똑같은 시점이 오면 이후의 경우의 수의 개수는 같아집니다.
예를 들어 1,2,8,... 의 무게를 가진 추가 주어졌을때, 8(좌) → 1(우) → 2(우) 경우나 8(좌) → 2(우) → 1(우) 경우나 추의 현재 상태는 같습니다.
추의 상태가 같으면 이후 가능한 경우의 수도 같아집니다.
추의 상태를 사용한 추 (갯수가 작기 때문에 비트 마스킹으로 기록), 좌측에 놓인 무게로 저장하고 이전에 탐색한 적이 있다면 더 탐색을 하지 않고 그 값을 사용하는 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class q3234_SWEA_준환이의양팔저울Re2 {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, total;
static int[] gram;
static int[][] memo;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
total = 0;
gram = new int[N];
st = new StringTokenizer(br.readLine());
for (int n = 0; n < N; n++) {
gram[n] = Integer.parseInt(st.nextToken());
total += gram[n];
}
memo = new int[total + 1][1 << N];
sb.append("#").append(tc).append(" ").append(makePermutation(0, 0, 0, 0)).append("\n");
}
System.out.println(sb);
}
static int makePermutation(int count, int bitmask, int left, int right) {
if (count == N) {
return 1;
}
int sum = memo[left][bitmask];
if (sum == 0) {
for (int i = 0; i < N; i++) {
if ((bitmask & (1 << i)) == 0) {
sum += makePermutation(count + 1, bitmask | (1 << i), left + gram[i], right);
if (right + gram[i] <= left) {
sum += makePermutation(count + 1, bitmask | (1 << i), left, right + gram[i]);
}
}
}
return memo[left][bitmask] = sum;
}
return sum;
}
}
위에서부터 순서대로 메모이제이션 → 순열구하면서 가지치기 → 순열 구하고 가지치기 코드의 실행결과입니다.
여러가지로 생각할 거리가 많은 좋은 문제였습니다.
'🔍 알고리즘 > SWEA' 카테고리의 다른 글
[Java] SWEA 5656.벽돌깨기 (모의SW테스트) (0) | 2022.07.11 |
---|---|
[Java] SWEA 4698.테네스의 특별한 소수 D3 (0) | 2022.07.08 |
[Java] SWEA 7699.수지의 수지맞는 여행 D4 (0) | 2022.07.04 |
[Java] SWEA 8382.방향전환 D4 (0) | 2022.07.03 |
[Java] SWEA 8458.원점으로 집합 D4 (0) | 2022.07.03 |