[백준] 1105 팔 - 아이디어(Idea) + 수학(Math) + 탐욕법(Greedy) JAVA

https://www.acmicpc.net/problem/1105

코드설명

아이디어(Idea) + 수학(Math) + 탐욕법(Greedy)을 활용합니다.

 

문제를 풀기 위한 조건입니다.

1. 만약 길이가 서로 다르다면, '8'이 0개인 숫자가 반드시 존재한다.

2. 만약 길이가 같다면, 각 자리수가 같은 수까지에서의 8의 개수가 최소한의 8의 개수를 가진 숫자다.

 

이러한 문제는 반례로 이해하는게 가장 좋습니다.

입력예시
189 256


답
0

왜 위와 같을까요? 

먼저 첫번쨰 조건에는 맞지 않습니다. 두개의 숫자의 길이가 같습니다.

두번쨰 조건에서의, '1'과 '2'를 비교합니다. 서로 다르므로 cnt가 0 입니다.

 

입력예시
787 789

답예시
1

왜 1이 나올까요?

'7' '7'로 첫번쨰 숫자가 같습니다. 하지만 '8'은 아니므로 cnt(8의 최소횟수)에 더하지는 않습니다.

'8' ''8' 로 같습니다. cnt에 1 증가시킵니다.

마지막 수는 다르므로 중단시킵니다.

 

cnt를 출력해주면 8의 최소횟수가 나옵니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		String L = st.nextToken();
		String R = st.nextToken();
		
		if(L.length() != R.length()) {
			System.out.println(0);
		}
		else if(L.length() == R.length()){
			//맨앞에서부터 자리비교.
			int cnt = 0;
			for(int i=0; i<L.length(); i++) {
				if(L.charAt(i) == '8' && R.charAt(i) == '8') {
					cnt += 1;
				}
				if(L.charAt(i) != R.charAt(i) ) {
					break;
				}
			}
			System.out.println(cnt);
		}
		
	}
}