반응형
1차 시도
#include<iostream>
#include<vector>
using namespace std;
int main() {
int t;
cin >> t;
vector <int> m(t);
vector <int> n(t);
vector <int> x(t);
vector <int> y(t);
vector <int> k(t);
for (int i = 0; i < t; i++) {
cin >> m[i] >> n[i] >> x[i] >> y[i];
}
for (int i = 0; i < t; i++) {
int cnt = 1;
while (true) {
if (m[i] < n[i]) {
if ((m[i] * (cnt + 1) + x[i]) == (n[i] * cnt + y[i]))
{
k[i] = m[i] * (cnt + 1) + x[i];
break;
}
}
else if (m[i] == n[i]) {
if (x[i] != y[i]) {
k[i] = -1;
break;
}
}
else {
if ((m[i] * cnt + x[i]) == (n[i] * (cnt + 1) + y[i]))
{
k[i] = m[i] * cnt + x[i];
break;
}
}
if (cnt > 1000000) {
k[i] = -1;
break;
}
cnt += 1;
}
}
for (int i = 0; i < t; i++)
cout << k[i] << '\n';
return 0;
}
입력받는 m, n의 대소관계에 따라 조건식을 걸어 K값을 출력했다.
그러나 이렇게 되면 <x:y> 의 유효하지 않은 해를 판별할 수 없다. 즉 -1을 출력하는 과정이 상당히 애매해진다.
2차 시도
#include<iostream>
#include<vector>
using namespace std;
int main() {
int t;
cin >> t;
vector <int> m(t);
vector <int> n(t);
vector <int> x(t);
vector <int> y(t);
vector <int> k(t);
for (int i = 0; i < t; i++) {
cin >> m[i] >> n[i] >> x[i] >> y[i];
}
for (int i = 0; i < t; i++) {
for (int j = 0; j <= 40000; j++) {
if ((j - x[i]) % m[i] == 0 && (j - y[i]) % n[i] == 0) {
k[i] = j;
break;
}
if (j == 40000) {
k[i] = -1;
break;
}
}
}
for (int i = 0; i < t; i++)
cout << k[i] << '\n';
return 0;
}
2차시도에선 조금 생각을 달리 해봤다.
아예 결과값 k를 예측하고 반복문으로 돌리면 시간복잡도는 O(n)이니 큰 문제가 없을 것 같아 브루트포스로 진행해봤다.
결과값 K에서 x 와 y를 각각 뺀 값에 m, n으로 나누어 떨어진 k값을 찾는 과정이다.
( j - x ) % m == 0 && ( j - y ) % n == 0
예제 출력은 정상적으로 출력된다.
3번만에 간신히 맞췄다.
반응형
'개발(Dev) 이야기 > Algorithm' 카테고리의 다른 글
[BOJ] 미로탐색_2178 (0) | 2020.03.26 |
---|---|
[BOJ] BFS, DFS 구현 방법 (0) | 2020.03.22 |
[BOJ] 리모컨_1107.cpp (0) | 2020.03.17 |
[BOJ] N과M(6)_15655.cpp (0) | 2020.03.17 |
[BOJ] N과M(5)_15654.cpp (0) | 2020.03.17 |