백준 1086번: 박성원
박성원
아이디어
주어진 순자를 하나씩 골라 뒤로 붙이면서 점점 큰 숫자를 만든다. 이 때 숫자가 커질 수 있으므로 나머지만 취한다. 어차피 나누어 떨어지는지 확인만 하면 됨.
a뒤에 b를 붙이면 (a×10^b.length)+b이고 나머지를 계속 계산해야 하므로 a%K, 10^b.length%K, b%K를 알면 된다.
10^n%K와, a%K, b%K를 전부 미리 계산해놓아야 TLE를 피할 수 있다.
이렇게 숫자를 하나씩 붙이다 모든 숫자를 사용한 경우, 현재 나머지가 얼마인지 확인하고, 0이면 성립하므로 1을 반환한다.
현재 어떤 숫자를 사용했는지와 현재 나머지가 몇인지를 기준으로 메모이제이션 한다.
10, 1, 101, 200 이렇게 4개의 숫자가 있다고 하자.
10-1-101 순서로 붙이나 101-10-1 순서로 붙이나 나머지가 같기 때문에 숫자를 사용한 순서를 기록할 필요는 없다
코드
#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, K;
int cache[1<<15][100], arr[15], pre[51];
vector<string> v;
int solve(int check, int mod) {
if (check == (1<<N)-1) {
return mod ? 0 : 1;
}
int& ret = cache[check][mod];
if (ret != -1) return ret;
ret = 0;
for (int i = 0; i < N; i++) {
if (check & (1<<i)) continue;
int m = mod*pre[v[i].length()]%K;
ret += solve(check|(1<<i), (m+arr[i])%K);
}
return ret;
}
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a%b);
}
int fact(int n) {
if (n == 1) return 1;
return n*fact(n-1);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
v.resize(N);
for (int i = 0; i < N; i++) {
cin >> v[i];
}
cin >> K;
// 10^n % K 계산 (최대 길이 50)
pre[0] = 1;
for (int i = 1; i < 51; i++) {
pre[i] = pre[i-1]*10%K;
}
// 입력받은 긴 숫자 % K 계산
for (int i = 0; i < N; i++) {
int m = 0;
for (char& c : v[i]) {
m = m*10 + (c-'0');
m %= K;
}
arr[i] = m;
}
memset(cache, -1, sizeof(cache));
int a = solve(0, 0);
int b = fact(N);
int g = gcd(a, b);
cout << a/g << '/' << b/g;
return 0;
}
여담
왜 900ms나 걸렸을까? 어디가 문제일까?..
아 그리고 long long 써야함.
Author And Source
이 문제에 관하여(백준 1086번: 박성원), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-1086번-박성원저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)