시간 초과를 조심하자 !
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
vector<long long> B(n);
for (int i = 0; i < n; i++)
cin >> B[i];
sort(B.begin(), B.end());
do {
long long value= B[0];
bool flag = true;
for (int i = 1; i < n; i++) {
// 나3곱2의 경우가 아니면
if (!(B[i] == value * 2 || (B[i] == value / 3 && value % 3 == 0))) {
flag = false;
break;
}
value = B[i];
}
if (flag)
break;
} while (next_permutation(B.begin(), B.end()));
for (int i = 0; i < n; i++)
cout << B[i] << " ";
cout << endl;
return 0;
}
B 배열의 모든 경우를 따져보아야 한다 생각하여 next_permutation
함수를 사용하였다. 그러나 이는 시간 초과 .. (N +1)! 그러니까 최대 101!의 시간이 걸리고 이는 엄청난 ,, 시간이 걸리게 된다. 🥲🥲
따라서 이는 곱2, 나3 두 가지 연산만 할 수 있다는 점을 이용해 문제를 풀어야 한다.
해결 코드
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int a[101]; // a[i] : i번 다음에 올 수 있는 값은 B의 a[i]번 위치에 있다.
int main() {
int n; cin >> n;
vector<long long> B(n);
for (int i = 0; i < n; i++)
cin >> B[i];
memset(a, -1, sizeof(a));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (B[i] * 2 == B[j]) a[i] = j;
else if (B[i] / 3 == B[j] && B[i] % 3 == 0) a[i] = j;
}
}
// A배열에서 제일 처음 오는 값의 B 위치를 찾는다.
int firstIndex = n * (n - 1) / 2;
for (int i = 0; i < n; i++) {
if (a[i] != -1)
firstIndex -= a[i];
}
vector<long long> ret;
ret.push_back(B[firstIndex]);
long long nextIndex = a[firstIndex];
while (a[nextIndex] != -1) {
ret.push_back(B[nextIndex]);
nextIndex = a[nextIndex];
}
ret.push_back(B[nextIndex]);
for (int i = 0; i < ret.size(); i++)
cout << ret[i] << " ";
cout << endl;
return 0;
}
조금 복잡해 보이는데, 이중 for문에서 배열 B의 특정 i번 숫자에서 j번 숫자로 나3곱2 연산으로 이동할 수 있다면 a[i] = j
를 입력해주었다.
그리고 배열 a
중에서 값이 -1이 되어있는, 즉 A 배열에서 앞에 다른 숫자가 없는 경우 firstIndex
라고 지정해주고 a
배열을 매개체로 해서 연쇄적으로 nextIndex
의 값을 구해준다. 이렇게 해서 ret
에 마지막 원소까지 넣고 출력하면 끝 !
또 이런 방식으로도 풀 수 있어요 🐹
나누기 3 연산은 피연산자를 소인수분해 했을 때 3이 하나 줄어들게 된다. 또한, 곱하기 2 연산은 소인수분해 했을 때 2가 하나 늘어난다.
따라서 4, 8, 6, 3, 12, 9 라는 배열을 각각 소인수분해했을 때 가장 3의 개수가 많은 9가 A 배열에 처음으로 올 수밖에 없다. 왜냐하면 3은 줄어들 수만 있지 늘어날 수 없으니까 !
마찬가지로 가장 2의 개수가 많은 8이 A 배열의 마지막에 올 수 밖에 없다. 왜냐하면 2는 늘어날 수만 있지 줄어들 수는 없으니까 ! 따라서 아래 조건으로 바꾸어 문제를 풀 수 있다.
- count[i] : 각각의 수가 3으로 몇 번 나누어질 수 있는지 기록하여, i번째 수가 3으로 나누어지는 횟수를 저장한다.
- A 수열에서는
count[A[i]] >= count[A[i + 1]
을 만족한다. - A 수열에서는
A[i] * 2 = A[i + 1]
을 만족한다.
이렇게 count
배열을 구한 다음에 1번 조건을 이용해 정렬하고, 2번 조건을 이용해 한 번 더 정렬하면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 3의 개수 기준으로 내림차순 정렬
bool cmp(pair<int, long long >& a, pair<int, long long >& b) {
if (a.first == b.first)
return a.second < b.second;
else
return a.first > b.second;
}
int main() {
int n; cin >> n;
// (3의 개수, 실제 수)
vector<pair<int, long long>> a(n);
for (int i = 0; i < n; i++) {
long long num;
cin >> num;
a[i].second = num;
while (num % 3 == 0) { // 3의 개수 계산
num /= 3;
a[i].first++;
}
}
sort(a.begin(), a.end(), cmp);
for (int i = 0; i < n; i++)
cout << a[i].second << " ";
cout << endl;
return 0;
}
'Algorithm > Baekjoon' 카테고리의 다른 글
[BOJ/C++] 백준 28075 - 스파이 (0) | 2023.05.23 |
---|---|
[BOJ/C++] 백준 28074 - 모비스 (0) | 2023.05.23 |
[백준] 14889 스타트와 링크 C++ 문제 풀이 (0) | 2023.04.03 |
백준 1027 고층 건물 C++ #Math (0) | 2023.01.17 |
백준 12847 꿀 아르바이트 C++ 풀이 (0) | 2022.11.09 |