티스토리 뷰
문제링크 : 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 |