[백준(Baekjoon)][자바(java)] 1019 : 책 페이지 / 수학

 

www.acmicpc.net/problem/1019

1019번: 책 페이지

 

문제 풀이

 

 

▶  브루트 포스  -->  시간초과

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		int n = Integer.parseInt( br.readLine() );
		br.close();
        
		int a[] = new int[10], i, t;
		for( i = 1; i <= n; i++ ) {
			t = i;
			while( t > 0 ) {
				a[ t % 10 ]++;
				t /= 10;
			}
		}
        
		for( int aa : a )
			bw.write( aa + " " );
		bw.write("\n");
		bw.flush();
		bw.close();
        
	}
}

 

 

▶  문제 변형해서 풀기

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		int a[] = new int[10], i;
		int n = Integer.parseInt( br.readLine() ), s = 1, e = n, d = 1, t;
		// num, start, end, digit, tmp
		while( s <= e ) {
			while( e % 10 != 9 && s <= e ) {
				t = e;
				while( t > 0 ) {
		            a[ t % 10 ] += d; 
		            t /= 10; 
		        }
				e--;
			}
			if( e < s )
				break;
			while( s % 10 != 0 && s <= e ) {
				t = s;
				while( t > 0 ) {
		            a[ t % 10 ] += d; 
		            t /= 10; 
		        }
				s++;
			}
			s /= 10;
			e /= 10;
			for( i = 0; i < 10; i++ )
				a[i] += ( e - s + 1 ) * d;
			d *= 10;
		}
		for( int aa : a )
			bw.write( aa + " " );
		bw.write("\n");

		bw.flush();
		bw.close();
        
	}
}

 

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019?qid=9aa7818e-779e-499a-9c13-d2a5ac2ef8af&v=&b=&from_search=1

 

문제에서 요구하는 것은 1~n까지의 수에서 0~9가 나오는 각각의 개수 인데, 

이 것을 변형해서 A~B까지의 수 중에서 구한다고 가정한다.

A의 일의 자리가 0, B의 일의 자리가 9일 때

일의 자리에 0~9는 각각 ( (B/10) - (A/10) + 1 ) * 1 번씩 등장한다

A, B를 각각 10으로 나눠준 후

십의 자리에 0~9는 각각 ( (B/10) - (A/10) + 1 ) * 10 번씩 등장한다

이 공식을 이용하여 A의 일의 자리가 0, B의 일의 자리가 9가 되도록 A++ 또는 B--를 하며 맞춰준다.

맞추는 동안의 A, B 수에서 0~9 숫자가 등장하는 개수는 브루트 포스로 구해서 더한다.