[BOJ][C++] 백준 18222번: 투에-모스 문자열

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

 

문제

0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다.

1. X는 맨 처음에 "0"으로 시작한다. 
2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다.
3. X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다. 
4. 2~3의 과정을 무한히 반복한다.

즉, X는 처음에 "0"으로 시작하여 "01"이 되고, "0110"이 되고, "01101001"이 되고, ⋯ 의 과정을 거쳐 다음과 같이 나타내어진다.

    "011010011001011010010110011010011001011001101001⋯⋯"

자연수 k가 주어졌을 때 X의 k번째에는 무슨 문자가 오는지 구하여라.

입력

첫 번째 줄에 자연수 k (1 ≤ k ≤ 1018) 가 주어진다.

 

출력

첫 번째 줄에 k번째에 오는 문자를 출력하라.

 

풀이

아래 '시행착오' 코드처럼 단순 구현을 했더니 메모리 초과가 떴다.

공간복잡도와 시간복잡도를 둘 다 줄이기 위해 분할정복을 이용하자

 

또한 K의 범위는 0~10^8이다. 10^18과 근사한 2의 거듭제곱은 2^66 정도로

int로 담을 수 없는 값이다

코드 전반에 long long 을 이용하자

 

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long recur(long long k) {
    if(k==1) {
        return 0;
    }
    
    long long pow_of_2 = 1;
    while(k>pow_of_2) {
        pow_of_2 *= 2;
    }
    
    return 1 - recur(k-pow_of_2/2);
}

int main() {
    long long k;
    cin >> k;
    
    cout << recur(k);
    
    return 0;
}

 

 

 

시행착오

 

메모리 초과가 뜨는 단순 구현 코드

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string get_new_string(string s) {
    string new_string = "";
    for(char c : s) {
        if(c=='0') new_string += '1';
        else new_string += '0';
    }
    return new_string;
}

int main() {
    int k;
    cin >> k;
    
    int length = 0;
    string s = "0";
    while(length < k) {
        length += s.size();
        s += get_new_string(s);
    }
    
    cout << s[k-1];
    
    return 0;
}

 

그래서 분할정복으로 개선한 코드.

하지만 시간초과가 뜬다

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int recur(int k) {
    if(k==1) {
        return 0;
    }
    
    int pow_of_2 = 1;
    while(k>pow_of_2) {
        pow_of_2 *= 2;
    }
    
    return 1 - recur(k-pow_of_2/2);
}

int main() {
    int k;
    cin >> k;
    
    cout << recur(k);
    
    return 0;
}