백준 2877번 4와 7[C++]

1. 개요

 안녕하세요. 이번에 푼 문제의 유형은 수학, 구현입니다. 사실 이런 유형의 문제를 처음 풀어보는 것은 아니지만 항상 풀이할 때마다 어려움을 느끼곤 합니다. 4와 7로만 이루어진 수를 이진수로 표현하는 것이 가능할까? 에서 출발한 다음 규칙을 찾고 그 규칙에 맞추어 k를 변형하여 풀이하는 게 정석인 것 같습니다. 

 

2. 문제 풀이

 이진수로 4와 7로 이루어진 숫자를 표현해봅시다. 저는 0을 4로 7을 1로 바꾸어서 나열하였고, 그와 매칭할 수 있는 k를 대괄호 안에 적어주었습니다.

[0] 0 4
[1] 1 7

[2] 00 44
[3] 01 47
[4] 10 74
[5] 11 77

[6] 000 444
[7] 001 447
[8] 010 474
[9] 011 477
[10] 100 744
[11] 101 747
[12] 110 774
[13] 111 777

[14] 0000 4444
[15] 0001 4447
[16] 0010 4474
[17] 0011 4477
[18] 0100 4744
[19] 0101 4747
[20] 0110 4774
[21] 0111 4777
[22] 1000 7444
[23] 1001 7447
[24] 1010 7474
[25] 1011 7477
[26] 1100 7744
[27] 1101 7747
[28] 1110 7774
[29] 1111 7777

 

규칙성이 눈에 들어오시나요? 우선 이진수의 자릿수는 2, 4, 8, 16, ... 과 같이 2의 제곱수로 증가합니다. 또한 자릿수가 증가할 때마다 0부터 다시 카운트해야 정확하게 답을 구할 수 있습니다. 입력값 k로부터 자릿수와 해당 자릿수에서 몇 번째 위치하는지 구할 수 있다면 이 문제를 풀이할 수 있습니다. 

 

자릿수는 2의 제곱수로 늘어나므로 loop를 통해 순차적으로 k에 뺄셈 연산을 하면서 자릿수와 위치를 구할 수 있게 됩니다. 이렇게 구한 이진수를 0이면 4, 1이면 7을 추가한 문자열을 반환하면 됩니다.

 

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int k;

string solve(int num, int digit) {
    string ret{};
    for(int i = 0; i < digit; i++) {
        ret += (num & (1 << i)) ? "7" : "4";
    } 
    reverse(all(ret));
    return ret;
}

int main() {
    fastio(nullptr, false);

    cin >> k;

    int digit{1};
    for(int offset = 1; k - (1 << offset) > 0; offset++) {
        digit++;
        k -= (1 << offset);
    }

    cout << solve(k - 1, digit);
}

 

4. 제출 결과