[Python&C++]7868-해밍 수열

 

https://www.acmicpc.net/problem/7868

7868번: 해밍 수열

나 혼자서 풀어낸 두번째 골드다. (처음은 1043-거짓말)

그래프문제를 최근 풀어보기 시작했는데, 굉장히 재밌다. (1012-유기농 배추로 입문. 그때는 내가 하고있는게 dfs인줄도 모르고 풀었다.)

이제 문제를 설명하겠다.

나는 O(n^3)으로 풀었다.

수열 H의 원소는

$ 0 \leq i, j, k \leq 60$ 일때,(60보다 작은 이유는 나중에 설명)

${p1^i}\times{p2^j}\times{p3^k}$ 로 나타 낼 수있다. 

이렇게 구한 값들을 모두 배열에 넣은 뒤, 정렬 해서 i번째 값을 출력했다. i-1이 아닌 이유는, 어쩔 수 없이 1이 들어가기 때문이다.($i, j, k = 0$이면 ${p1^i}\times{p2^j}\times{p3^k}$는 1)

그리고, i,j,k가 60보다 작은 이유는 로그를 사용하면 쉽게 알 수 있다.
p1,p2,p3 은 소수 이므로, 최소 2 이다. ($p1 \neq p2 \neq p3$이라는 조건이 없으니)

그럼, ${p1^i}\times{p2^j}\times{p3^k}$의 최솟값은 ${2^i}\times{2^j}\times{2^k}$로 나타낼 수 있고, 이는 $2^{i+j+k}$로 나타낼 수 있다.

이제, $2^{i+j+k} \leq 10^{18}$인 i, j, k를 찾으면 된다.

양변에 로그를 취하면, $(i+j+k) \leq log_{2}10^{18}$이고, $log_{2}10^{18} = 59.794705708.....$이므로, 

$i+j+k \leq 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을 출력하는 오류 때문이다.