<알고리즘 문제풀이&연습>/[C,C++] Hackerrank

[CodeGround] 극단적인 수

사용자 BlockDMask 2017. 8. 4. 18:03
반응형
  • 안녕하세요. 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. 코드


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
32
33
34
35
36
#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;
}
cs


4. 인증



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

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

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

감사합니다.

반응형