티스토리 뷰

백준/골드

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

게임개발기원 2025. 4. 30. 02:48

문제링크 : 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로 변환하여 출력해준다.

 

 

'백준 > 골드' 카테고리의 다른 글

[백준 10422번] 괄호 (C++)  (0) 2025.05.07
[백준 1253번] 좋다 (C++)  (0) 2025.05.04
[백준 1790번] 수 이어 쓰기 2 (C++)  (0) 2025.04.29
[백준 1188번] 음식 평론가 (C++)  (0) 2025.04.28
[백준 1405번] 미친 로봇 (C++)  (0) 2025.04.27
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/08   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함