백 트래킹 방식으로 해결하고자 했다. 스도쿠 빈 칸에 1부터 9까지 숫자를 넣고, 그 숫자가 promising한지 검사 후, promising하다면 스도쿠의 답으로 인정하고, promising하지 않다면 다음 숫자를 검사하거나, 모든 숫자를 검사했다면 그 전 백 트래킹 함수로 돌아가 다른 답을 찾는다.
빈 칸을 기억하고 있는 vector<pair<int, int>> zero;를 선언하였고, 그 벡터의 크기인 zeroNum을 저장해 두었다.
함수 bt의 파라미터는 벡터 zero에서 indexlevel까지 답을 찾았다 라는 의미다. 따라서, bt가 멈추는 조건도 if(level == zeroNum - 1)라고 정의할 수 있겠다. if(level == zeroNum - 1)이면 zero에 들어있던 모든 빈칸에 대한 답을 찾은 것 이므로, print해주고 exit(0)해주면 된다. 문제의 조건이 여러 답 중에 하나만 출력하면 되므로 제일 먼저 찾은 것을 출력했다.
처음에 들어온 문자열을 문자로 쪼개서 문자들을 sort해서 next_permutation을 돌렸다. 돌리면서 한 문자에 어떤 숫자가 들어가는 지 결정하고, 또 문자열을 쪼개서 다 합한 것을 계산했다. 뭐라 설명해야할 지 모르겠고, 그냥 미친 짓이였다.
올바른 접근
받은 스트링이 ABCDE가 있다면, 이를 10000 * A + 1000 * B + 100 * C + 10 * D + 1 * E처럼 해석 하는 것이다.
나는 map<char, int> m을 선언해서 char에는 문자를, int에는 숫자를 넣어줬다.
map에 다 넣은 뒤, map의 int 기준으로 내림차순 정렬을 하려고 했다. 그래서 새 구조체를 선언했고, map을 vector로 변환하는 과정을 거쳤다.
// 구조체
struct Le{
char letter;
int value;
Le(char a, int b){
letter = a;
value = b;
}
bool operator < (const Le & b) const {
return value > b.value;
}
};
// 벡터로 변환하는 과정
for(auto & i : m){
if(i.second != 0){
exist.push_back(Le(i.first, i.second));
}
}
내림차순 정렬을 하고, 정렬한 원소 순서대로 9, 8, 7, ...을 넣어서 계산해주면 된다.
int cnt = 9;
sort(exist.begin(), exist.end());
for(auto i : exist){
answer += (cnt * i.value);
cnt--;
}
코드
#include <bits/stdc++.h>
using namespace std;
struct Le{
char letter;
int value;
Le(char a, int b){
letter = a;
value = b;
}
bool operator < (const Le & b) const {
return value > b.value;
}
};
int n, answer;
string temp;
map<char, int> m;
vector<Le> exist;
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> temp;
for(int i = 0; i < temp.length(); i++){
m[temp[i]] += pow(10, temp.length() - i - 1);
}
}
for(auto & i : m){
if(i.second != 0){
exist.push_back(Le(i.first, i.second));
}
}
int cnt = 9;
sort(exist.begin(), exist.end());
for(auto i : exist){
answer += (cnt * i.value);
cnt--;
}
cout << answer;
}
처음 문제에 접근할 때 단순히 문제의 조건대로 1년씩 늘려서 x와 y를 늘려주는 식으로 했다. 역시나 시간 초과. 결국 띄엄띄엄 검사하는 생각해야 했다.
개선한 생각
문제의 조건에 의해 <1, 1>이 <m, n>이 되면 카잉 달력은 끝나게 된다. 그렇다면 <m, n>이 되려면 몇 년이 지나야 할까. 결론부터 말하면 m과 n의 최소공배수가 되면 끝난다 . 그 이유는 왼쪽 수가 m이 되는 경우는 카잉년이 m의 배수가 될 때이고, 오른쪽 수가 n이 되는 경우는 카잉년이 n의 배수가 될 때이기 때문이다. 그래서, limit이라는 변수를 선언해서 카잉년을 몇 년까지 검사를 해야할 지 담아 놓았다. 최소공배수를 구하기 위해, 간단히 함수도 구현해 주었다.
int gcd(int a, int b){
while(b != 0){
int r = a % b;
a = b;
b = r;
}
return a;
}
int lcm(int a, int b){
return a * b / gcd(a, b);
}
문제에서 요구하는 것은 _<x, y>는 몇 년째인가?_ 이다. 위와 같이 배수적인 표현으로 생각해보면, 왼쪽 좌표는 카잉년에서 m으로 나눈 나머지 가 되고, 오른쪽 좌표는 카이년에서 n으로 나눈 나머지 가 된다. 숫자를 하나씩 늘려가면서 생각해보면 쉽게 나오는 결론이였다.
현재 카잉년을 tar이라고 했을 때,
tar % m = x이고
tar % n = y인 tar는 <x, y>의 카잉년이 된다. 만일 찾은 카잉년이 limit 이상으로 넘어가게 된다면, 답이 될 수 없다.
위의 조건으로 코드를 구현해보았다.
cin >> m >> n >> x >> y;
flag = 0;
limit = lcm(m, n);
for(int j = x; j <= limit ; j += m){
if(j % n == y % n){
flag = 1;
cout << j << endl;
break;
}
}
if(flag == 0){
cout << "-1" << endl;
}
for문에서 나타나는 j가 위에서 설명한 tar이 된다. j는 for문을 돌면서 왼쪽 좌표가 x가 되는 케이스 를 찾는다. 그 j에서 오른쪽 좌표가 y가 되는 케이스 를 찾으면 그 값이 출력해야 하는 값이 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
while(b != 0){
int r = a % b;
a = b;
b = r;
}
return a;
}
int lcm(int a, int b){
return a * b / gcd(a, b);
}
int sit, m, n, x, y, limit, flag;
int main(){
ios_base::sync_with_stdio(false);
cin >> sit;
for(int i = 1; i <= sit; i++){
cin >> m >> n >> x >> y;
flag = 0;
limit = lcm(m, n);
for(int j = x; j <= limit ; j += m){
if(j % n == y % n){
flag = 1;
cout << j << endl;
break;
}
}
if(flag == 0){
cout << "-1" << endl;
}
}
}
