[BOJ] 2877 - 4와 7

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/2877

2877번: 4와 7

난이도: 실버 1

사용언어: JAVA

 

풀이

풀이는 간단합니다. 우선 K를 입력받았을 때, K번 째 수가 몇 자리 숫자인지를 먼저 파악해야 합니다. K=4 라면 정답이 47이므로 2자리 수, 14라면 777이므로 3자리 수라는 것을 먼저 알아내야 합니다.

 

그 뒤에는 K가 해당 자릿수 숫자들 중 몇 번째에 해당하는 지를 알아내기만 하면 됩니다. 4와 7로 숫자를 표현했지만, 사실 이진수와 같은 표현법을 사용하기 때문에, 해당 자리 수의 숫자들 중 몇 번째 숫자인지를 파악하여, 이 숫자를 이진수로 바꿔주기만 하면 됩니다.

 

그리고 출력은 0 대신 4, 1 대신 7로 하면 정답을 얻을 수 있습니다.

 

예를 들면 13은 3자리 숫자의 답을 얻을 수 있습니다. 그리고 3자리 숫자들 중 7번째 숫자입니다. 이진수의 첫 숫자는 000이므로 0부터 시작하기 때문에, 6을 이진수로 바꾼 값을 4와 7로 표현해주기만 하면 됩니다. 6을 3자리 2진수로 표현하면 110이기 때문에, 정답으로는 774를 출력해주면 됩니다.

 

import java.io.*;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int K;
        K = Integer.parseInt(br.readLine());
 
        int i = 2, j=2, k, l, cnt=1;
        while(i<K){
            i += j*2;
            j*=2;
            cnt++;
       } // 몇 자리 수인지를 파악.
 
        k = i - j;
        l = K - k - 1; // 해당 자리 수의 몇번째 숫자인지를 파악. 0부터 숫자를 세기 때문에 -1을 해주어야함.
        int []arr = new int[cnt];
        for(i=cnt-1;i>=0;i--){
            if(l==0 || l%2 == 0){ // 이진수에서 0으로 표현되면 4를 저장
                arr[i] = 4;
            }
            else{ // 이진수에서 1로 표현되면 7을 저장
                arr[i] = 7;
            }
            l = l/2;
        }
 
        for(i=0;i<cnt;i++){
            bw.write(String.valueOf(arr[i]));
        }
        bw.flush();
    }
 
}