문제 이해 단계
짧고 간결해서 아주 좋은 문제
4와 7로 구성된 숫자 중에서
입력된 K번째로 작은 수를 구하는 문제
문제 접근 단계
문제에서 건질만한 것은 K의 범위가 10^9라서
int 범위를 넘어가지 않는다는 것 정도?
그다음부터는 찾아내야 할 것 같다.
이렇게 수를 다루는 문제 같은 경우,
1번째부터 K번째 작은 수까지
한번 적어서 생각해 보는 게 낫다.
대충 어느 정도 열거해 보면 이런 식인데..
정말 4와 7을 열거하는 것이다 보니
얼마씩 더해지고 그런 건 없는 것 같다.
그렇다면 브루트포스처럼
첫 번째부터 구해야 하는 K번째까지 일일이 세야하나?
그것도 불가능하다.
K가 10^9까지이기 때문에
10^9 번 계산한다면 분명 시간초과가 날 것이다.
그렇다면 하다못해 해당 K가 몇 자릿수 인지는 알 수 없을까?
해서 자릿수가 변하는 번째만을 모아봤다.
1번째 → 4
3번째 → 44
7번째 → 444
15번째 → 4444
변하는 각 지점마다의 규칙이라도 찾아낼 수 있다면
조금은 수월해질 것이다.
1,3,7,15라는 숫자를 보니 다행히 등비수열이 떠올랐다.
즉 자릿수는 등비수열에 따라 올라가는 것이었다.
이를 이용하면 K가 몇 개의 자릿수로 이루어진지를
쉽게 확인할 수 있고,
그 444를 기준으로 얼마나 더 움직여야 할 지도 알 수 있다.
한 칸씩 움직이는 로직
이제 K를 최소한으로 줄였으니까
이제 결국에는 444로부터 연산을 해야 한다.
이걸 뒤에서부터 한 자리씩 보자.
숫자가 4와 7밖에 없기 때문에
한 자리에서 나올 수 있는 숫자는 4 또는 7 두 개밖에 없다.
위에 열거해 둔 수의 끝자리를 보면,
홀수번째 일 때 4를 가지고,
짝수번째 일 때 7을 가지는 것을 알 수 있다.
그리고 기준점 3번째(44)에서
5번째(74)는 총 2칸의 차이가 난다.
이에 따라 앞에 4가 7로 바뀐 것을 알 수 있다.
이는 이진수 덧셈과 굉장히 흡사하다.
4와 7 상태만 존재하기 때문에
0과 1밖에 존재하지 않는 이진수와 똑같기 때문이다.
즉, 해당 문제의 연산은 이진수의 덧셈과 똑같이 해주면 된다.
이제 이러한 로직에 따라 코드로 구현하면 된다.
문제 구현 단계
// 몇 자리인지 얻는 함수
int getDigit(int k){
int idx = 1; // 자리수
int sum = 1; //합
do{
sum += pow(2,idx); // 2의 제곱씩 더함
idx++;
}while(k >= sum); // sum이 더 커질때까지 반복
return idx-1;
}몇 개의 자리인지 얻는 함수인 getDigit이다.
매개변수로 K가 들어온다.
idx는 말 그대로 자릿수를 의미하고 이걸 반환한다.
sum은 더해주는 수로 기본적으로 1이 세팅되어 있다.
등비수열이므로 2의 제곱씩 더하는 것을
k보다 sum이 더 클 때까지 반복한다.
왜냐하면 k가 이전의 비교했던 자릿수보다 크거나 같고,
이번 자릿수보다 작아야 자기의 자리를 찾을 수 있기 때문.
그 과정에서 idx는 자릿수가
한번 더 더해졌기 때문에 반환하는 것은 idx-1이다.
void makeTable(string base, int remain){
for(int i = base.length()-1; i >= 0; i--){
if(remain % 2 != 0) base[i] = '7';
remain /= 2;
}
cout << base << "\n";
}이진수 덧셈을 하는 makeTable 함수이다.
매개변수로 남은 이동 횟수인 remain과
자릿수를 통해 만들어둔 444를 세팅한다.
remain이 짝수인지 홀수인지에 대해 4와 7 세팅을 구분해 주고,
2씩 나눠주어 올릴 수를 계속 전달한다.
이거는 이진수의 덧셈과 동일하기 때문에 크게 설명 안 하겠다.
이제 아래에 전체코드에 대한 설명을 올리고 끝마치겠다.
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
// 몇 자리인지 얻는 함수
int getDigit(int k){
int idx = 1; // 자리수
int sum = 1; //합
do{
sum += pow(2,idx); // 2의 제곱씩 더함
idx++;
}while(k >= sum); // sum이 더 커질때까지 반복
return idx-1;
}
void makeTable(string base, int remain){
for(int i = base.length()-1; i >= 0; i--){
if(remain % 2 != 0) base[i] = '7';
remain /= 2;
}
cout << base << "\n";
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int K;
cin >> K;
int digit = getDigit(K);
int remain;
int consume = 0; // 소비한 수
//remain을 구하기 위해 자릿수만큼 번째를 다 구함
for(int i = 0; i < digit; i++) consume += pow(2,i);
remain = K-consume;
string base;
for(int i = 0; i < digit; i++) base.push_back('4'); // digit큼 4로 채움
makeTable(base,remain);
}consume이라는 변수를 통해
우리가 구한 digit이라는 자릿수만큼의 번째를 빼주어 remain을 구한다.
이것 말고는 크게 볼 것이 없다.
시행착오
1시간 안에 푸는 게 목표였는데
그래도 1시간 30이면 선방한 것 같다.
수학 문제 치고는 잘 푼 것 같아서 기분이 좋긴 한데..
그래도 앞으로 1시간 안에 풀려도 노력해야겠다.
나름 코드도 깔끔하게 잘 짠 것 같다.