[CodeGround] 극단적인 수

• 안녕하세요. BlockDMask 입니다.

• 오늘은 새로운 알고리즘 문제 사이트 코드 그라운드(codeground)를 발견하여서 여기 문제를 풀어 보았습니다.

0. 제목

• 코드그라운드 극단적인 수.

• codeground 극단적인 수.

1. 문제설명

• 4와 7로만 이루어진 숫자셋이 있다고 생각.

• K가 들어오면 K 번째 숫자를 출력.

• 첫쨰줄에 1<= T <= 20 (Test case)

• 둘째줄 부터 출력할 K 번째 "특수한 수" 입력 (1<=K<=10^9)

2. 풀이과정

• 처음에 어렵게 접근을 하여서 많이 헤맸...다가.

• 4, 7 두가지 수인 것을 2진법과 연결이 되어서. 오!

• 하고 풀었습니다.

• 4와 7로 이루어진 수를 나열하면

• 4 / 7 / 44 / 47 / 74 / 77 / 444 /  . . . . . .

• 이런식으로 가게됩니다.

• 이것을 잘 보면 "두가지 수" 로만 이루어져 있음을 알 수 있습니다.

• 2진법도 0,1 두가지로 이루어져있죠.

• 1 -> 4

• 0 -> 7

• 이런식으로 대입을 하면 되지 않을까요?
  10진수를 -> 2진수로 바꾸어 주듯이
  10진수를 -> 4,7 법칙으로 바꾸어 주는 겁니다.

• 2의 배수이면 7이 되고, 그렇지 않으면 4가 됩니다.

• 여기서 중요한게 있습니다.

• 표를 보게되면

• 2번째 표를 보면

• 1, 3, 7 일때 4, 44, 444 가 됩니다.
  (7 - 1 ) /2 = 3
  (3 - 1) /2 = 1
  이런식으로 단위가 증가하는 것을 볼수 있으며

• 10진수에서 2진수로 변환하는 것 처럼
  나머지를 이용하여 각 자리의 숫자를 구하고
  역순으로 출력해야하기 때문에
  stack 자료구조를 이용하였습니다.

• 조금 다른 시각에서 본다면
  

• 4, 7 법칙의 10의자리수 100의 자리 1000의 자리수 들의 갯수는 

• 2의 k-1 제곱 순으로 증가합니다.

• (등비수열같이)

3. 코드

#include <iostream>
#include <stack>
using namespace std;
 
int main(int argc, char** argv)
{
    int T, test_case;
    int k;
    stack<int> s;    //스택을 만든다.
    
    cin >> T;
    for(test_case = 0; test_case < T; test_case++)
    {
        cin >> k;
 
        while(k!=0){
            if(k%2 == 1){    //2의 배수 아니면 나누어 떨어지면 4로
                s.push(4);    
            }else{            //2의 배수면 7로
                s.push(7);                
            }
            k = (k-1)/2;
 
        }
        
        cout << "Case #" << test_case+1 << endl;
        while(!s.empty()){  //출력
            cout << s.top();
            s.pop();
        }
        cout << endl;
        
    }
 
    return 0;
}

4. 인증

사이트 : home>practice>극단적인 수

https://www.codeground.org/practice/practiceProblemView

문제출처 : 충북대학교 프로그래밍 경진대회

감사합니다.