문제 : https://www.acmicpc.net/problem/1086
2일 전에 푼 문제를 왜 지금 포스팅하는지 물어보신다면 위 사진이 아마 답이 될 것 같습니다.
문제
주어지는 양의 정수 배열로 만들 수 있는 수 중 k로 나눠지는 수의 경우 / 모든 경우를 기약분수로 나타내야 합니다.
풀이
박성원 님의 문제점이 라고 하면 오해의 소지를 불러올 수 있으니 문제 박성원을 풀면서 제가 고민한 문제점 3가지를 정리해 보고 한 단계씩 해결해 보도록 하겠습니다.
1. 최대 50 * 15 자리 수와 k의 나머지를 어떻게 구할 것 인가?
2. N!의 모든 경우의 수를 어떻게 개선할 것 인가?
3. 기약분수의 형태로 어떻게 만들 것 인가?
+ 디테일
1. 최대 50 * 15 자리 수와 k의 나머지를 어떻게 구할 것 인가?
이 부분은 3학년때 배운 나눗셈 과정하며 방법을 떠올렸습니다.
가장 높은 자리 수부터 한 요소씩 나눠가며 값이 다음 요소로 넘어 가면 10을 곱하며 나눗셈을 진행한 로직을 바탕으로 코드를 작성했습니다. 시간복잡도는 O(나누는 숫자의 길이)이지만 직접 수를 나누는 것이 불가능하다 생각하여 위 방법으로 나머지를 구했습니다.
2. N!의 모든 경우의 수를 어떻게 개선할 것 인가?
어떤 시간을 개선 하는 방법 중 모든 특정 조건이나 규칙이 없는 이상 보통 DP로 저는 생각합니다. 자 DP 까지는 오케이
그럼 어떻게 특정 순간에 대한 지표를 나타낼 수 있을까요?
"집합의 한 요소가 쓰이고, 안 쓰이고" 이러한 문제 상황을 보면 아마 비트 마스킹 기법이 적합해 보였습니다. 하지만 비트마스킹 기법을 쉽게 도입하지 못했던 저의 고정관념이 있었습니다.
"비트 마스킹은 특정 순서가 없는 즉 순열이 아닌 조합에서 사용" 이 고정관념 때문에 많이 방황했습니다.
예를 들어 Arr ={10,2,3} 인 경우 102와 210의 비트는 같지만 완전히 다른 경우이니까요.
하지만 이 문제에서 중요한 값은 "k로 나눈 나머지" 입니다. k=5인 경우 102와 210은 다르지만, k=3인 경우에는 같은 결과를 나타내는 같은 값이라고 생각될 수 있습니다.
그래서 이를 이용하여 DP를 구현하기로 하였습니다.
3. 기약분수의 형태로 어떻게 만들 것 인가?
이 부분은 다른 분들의 코드를 참조하였습니다.
저는 팩토리얼을 곱해주면서 만일 나눠진다면 그 수를 스킵하는 방법을 생각하여 기약 분수로 가공 과정을 생각했었습니다.
N! 를 계산하며 정답이 N으로 나눠지면 정답과 모든 경우를 N으로 나눠줬습니다.
하지만 만일 특정수의 소인수? 요소만 필요한 경우 위 과정은 기약분수를 나타낼 수 없습니다.
그래서 결국 정답과 전체 경우의 수의 최대공약수를 구해서 기약분수를 구해야합니다.
최대공약수를 구하는 알고리즘은 아래와 같습니다.
public static long getGcd(long n, long m) {
if(m==0) return n;
return getGcd(m, n%m);
}
+
위 3개의 문제를 해결해도 이 문제를 쉽게 통과하기는 어렵습니다.
- 시간 초과 시
나머지 계산 중 중복되는 과정을 생략해야 합니다.
String을 매개변수로 던지면 안 됩니다.
- 메모리 초과 시
long의 wrapper 클래스인 Long으로 배열을 나타낼 시
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Num1086박성원 {
static int n,k;
static String[] inputStringValue;
static long[][] dp;
static int[][] memo;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
inputStringValue = new String[n];
for(int i=0;i<n;i++){
String input = br.readLine();
inputStringValue[i] = input;
}
k = Integer.parseInt(br.readLine());
dp = new long[1<<(n)][k];
memo = new int [n][k];
for(int i=0;i<n;i++){
Arrays.fill(memo[i],-1);
}
for (long[] longs : dp) {
Arrays.fill(longs, -1L);
}
Long ans = 0L;
for(int i=0;i<n;i++){
ans += DFS(1<<i,calculateRemain(i,0));
}
if(ans == 0L){
System.out.println("0/1");
}else{
long fac = 1L;
for(int i=2;i<=n;i++){
fac *= i;
}
long gcd = getGcd(fac,ans);
System.out.println(ans/gcd+"/"+fac/gcd);
}
}
public static Long DFS(int check,int remain){
if(check == (1<<n)-1){
if(remain == 0){
return 1L;
}
return 0L;
}
if(dp[check][remain] != -1) return dp[check][remain];
dp[check][remain] = 0L;
for(int i=0;i<n;i++){
int next = check | 1<<i;
if((check & 1<<i) !=0) continue;
int newRemain = calculateRemain(i,remain);
if(dp[next][newRemain] != -1){
dp[check][remain] += dp[next][newRemain];
continue;
}
dp[check][remain] += DFS(next,newRemain);
}
return dp[check][remain];
}
public static int calculateRemain(int index,int remain){
if(memo[index][remain] != -1) return memo[index][remain];
int value = remain;
for(int i=0;i<inputStringValue[index].length();i++){
value = value * 10 + Character.getNumericValue(inputStringValue[index].charAt(i));
value = value % k;
}
memo[index][remain] = value;
return value;
}
public static long getGcd(long n, long m) {
if(m==0) return n;
return getGcd(m, n%m);
}
}
+
뽐내기 타임
저 멋지죠?
'머리깨지며 배우는 코테풀이' 카테고리의 다른 글
| [문제 풀이] 백준 2616 소형기관차 (0) | 2025.01.03 |
|---|---|
| [문제 풀이] 가장 긴 증가하는 부분 수열 (LIS) (3) | 2024.11.07 |
| [문제 풀이] 백준 Num 17404 RGB거리2 (0) | 2024.10.27 |
| [문제 풀이] 백준 2186 문자판 (0) | 2024.10.25 |
| [JAVA] 백준 10217 KCM Travel (2) | 2024.10.18 |
