https://www.acmicpc.net/problem/7868
7868번: 해밍 수열
문제 세 소수 p1, p2, p3을 이용해서 해밍 수열 H(p1, p2, p3), i = 1... 을 정의할 수 있다. 해밍 수열 H(p1, p2, p3)은 소인수가 p1, p2, p3로만 이루어진 자연수의 오름 차순 목록이다. 예를 들어, H(2, 3, 5) = 2, 3
www.acmicpc.net
나 혼자서 풀어낸 두번째 골드다. (처음은 1043-거짓말)
그래프문제를 최근 풀어보기 시작했는데, 굉장히 재밌다. (1012-유기농 배추로 입문. 그때는 내가 하고있는게 dfs인줄도 모르고 풀었다.)
이제 문제를 설명하겠다.
나는 O(n^3)으로 풀었다.
수열 H의 원소는
0≤i,j,k≤60 일때,(60보다 작은 이유는 나중에 설명)
p1i×p2j×p3k 로 나타 낼 수있다.
이렇게 구한 값들을 모두 배열에 넣은 뒤, 정렬 해서 i번째 값을 출력했다. i-1이 아닌 이유는, 어쩔 수 없이 1이 들어가기 때문이다.(i,j,k=0이면 p1i×p2j×p3k는 1)
그리고, i,j,k가 60보다 작은 이유는 로그를 사용하면 쉽게 알 수 있다.
p1,p2,p3 은 소수 이므로, 최소 2 이다. (p1≠p2≠p3이라는 조건이 없으니)
그럼, p1i×p2j×p3k의 최솟값은 2i×2j×2k로 나타낼 수 있고, 이는 2i+j+k로 나타낼 수 있다.
이제, 2i+j+k≤1018인 i, j, k를 찾으면 된다.
양변에 로그를 취하면, (i+j+k)≤log21018이고, log21018=59.794705708.....이므로,
i+j+k≤60이어야 한다.
Python 코드
p1,p2,p3,i = map(int, input().split())
result = list()
for j in range(60):
b = p1**j
for k in range(60):
c = p2**k
a = b*c
result.append(a)
for l in range(60):
if j + k + l >= 59:
break
a *= p3
result.append(a)
result.sort()
print(result[i])
C++ 코드
#include <algorithm>
#include <iostream>
#include <vector>
unsigned long long pow(unsigned long long a, int b) {
unsigned long long res = 1;
for(int i = 0; i < b; i++) {
res *= a;
}
return res;
}
int main() {
unsigned long long p1, p2, p3, a, b, c;
int i;
std::cin >> p1 >> p2 >> p3 >> i;
std::vector<unsigned long long> result;
result.clear();
for(int j = 0; j < 60; j++) {
b = pow(p1, j);
for(int k = 0; k < 60; k++) {
c = pow(p2, k);
a = b*c;
result.push_back(a);
for(int l = 0; l < 60; l++) {
if(j+k+l >= 59) {
break;
}
a *= p3;
result.push_back(a);
}
}
}
std::sort(result.begin(), result.end());
std::cout << result[i];
return 0;
}
왜인지는 몰라도, p1, p2, p3중 하나라도 같은 것이 있으면 0을 출력한다. 나중에 이유를 알아내면 수정하겠다.

python 시간초과 난 이유는 for문 반복할때, i,j,k범위를 생각하지 않고 대충 range(1000)으로 돌려서 시간초과가 났다.
c++틀린 이유는 위에대로 p1, p2, p3중 같은 것이 있으면 0을 출력하는 오류 때문이다.
'알고리즘 > BOJ' 카테고리의 다른 글
[C++]11930-Smallest Enclosing Sphere (0) | 2020.09.12 |
---|---|
[Python]2389-세상의 중심에서... (0) | 2020.09.12 |
[Python]16489-삼각형 해커 (0) | 2020.09.10 |
[Python]1194-달이 차오른다, 가자. (0) | 2020.08.10 |
[Python&C++]1037-약수 (0) | 2020.05.19 |
[Python&C++]1026-보물 (0) | 2020.05.18 |
[Python&C++]1032-명령 프롬포트 (0) | 2020.05.18 |
[Python&C++]1004-어린 왕자 (0) | 2020.05.18 |