https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
주어진 조건에 맞게 양팔저울에 추를 올리는 경우의 수를 구하는 문제입니다.
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;
}
}
위에서부터 순서대로 메모이제이션 → 순열구하면서 가지치기 → 순열 구하고 가지치기 코드의 실행결과입니다.
여러가지로 생각할 거리가 많은 좋은 문제였습니다.
728x90
'🔍 알고리즘 > 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 |