알고리즘 풀이 - 백준 1748(수 이어 쓰기1, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N자리의 숫자가 주어질 때, 1부터 N까지 모두 이어 붙이면 몇 자리 수가 되는지 구하는 문제

 

2. 풀이

 

이 문제는 N이 1억 까지 주어지기 때문에 완전 탐색을 통해 단순히 하나 하나 체크해도 될 것 같지만 시간 제한이 0.15초 이기 때문에 그렇게는 풀 수 없다.

따라서, 우리는 건너 뛰어가며 필요한 연산만 수행해야 한다.

 

1~N까지의 숫자를 이어 붙이는 것으로, N이 몇 자리의 숫자인지가 중요하다. 만약 N이 120이라면, 한 자리수의 숫자들과 두 자리수의 숫자들은 모두 이어 붙이게 된다.

즉, 1~9, 10~99는 모두 이어 붙인다.

한 자리수인 1~9는 9개, 두 자리수인 10~99는 90개이다. 이와 같이 M 자리수의 숫자는 $9*10^{M-1}$ 개라고 볼 수 있다.

한 자리수는 9개 = $9*10^{1-1}$
두 자리수는 90개 = $9*10^{2-1}$

또는 $10^M - 10^{M-1}$ 개라고도 할 수 있다. 따라서 N 이하의 숫자 중에서 N이 M자리라면 M-1자리 까지는 모두 이어 붙이되 M자리 부터는 N까지 숫자만 이어 붙이도록 수식을 작성하면 끝나는 문제이다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;

public 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 n = Integer.parseInt(br.readLine());
        
        // n의 자리수 구하기
        int dig = 0;
        
        int temp = n;
        while(temp > 0){
            dig++;
            temp /= 10;
        }
        
        int ans = 0;
        for(int i=1; i <= dig; i++){
            // 현재 최대 자리수라면 n까지에서 10의 i-1승 한 것의 1을 더한 수만큼 자리수를 곱해서 총 정답에 더함
            if(i == dig){
                ans += (i * (n - Math.pow(10, i-1)+1));
            // 그 외의 경우 모든 경우의 자리수를 더함
            } else {
                ans += (i * (Math.pow(10, i) - Math.pow(10, i-1)));
            }
        }
        
        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }
}

 

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.