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

문제링크 : https://www.acmicpc.net/problem/2877

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int K;
    cin >> K;

    K++; //2번 노드부터 시작
    vector<int>b, v;
    while(K>=1) //2진수 변환
    {
        b.push_back(K%2);
        K/=2;
    }

    for(int i=b.size()-1; i>=0; i--) v.push_back(b[i]); //역순 저장

    for(int i=1; i<v.size(); i++) //루트노드 제외 출력
    {
        if(v[i]==0) cout << 4;
        else cout << 7;
    }

    return 0;
}

 

먼저 4와 7에 대해 경우의 수를 적고 규칙을 살펴보았다.

1 : 4
2 : 7
3 : 44
4 : 47
5 : 74
6 : 77
7 : 444
8 : 447
9 : 474
10 : 477
11 : 744
12 : 747 
13 : 774
14 : 777
.
.
.

 

보면 자릿수가 늘어 날때마다 총 개수가 직전의 2배가 되는 것을 알 수 있으며, 이를 통해 해당 값들을 이진트리의 형태로 표현이 가능하다는 것을 알았다. (4를 0으로, 7을 1로 바꿔서 생각)

루트노드를 제외한 2번노드부터 시작하기에, 입력받은 K에 1을 더해준 값을 이진수로 변환해준다.

이때 1을 더해주었기 때문에 맨 앞의 값은 필요가 없게 된다.

따라서 변환해준 이진수 값의 맨 앞을 제외한 나머지를 0이면 4로, 1이면 7로 변환하여 출력해준다.