[백준 / BOJ] 1105 팔

문제

출처 : www.acmicpc.net/problem/1105

1105번: 팔

L과 R을 입력받았을때,

L보다 크거나 같고, R보다 작거나 같은수중 8이 최소한으로 들어가는수를 찾으면된다.

 

풀이

R의 최댓값이 20억이라 완전탐색으로 찾을려하면 시간초과가 난다.

8의 개수를 찾아야 하는것 이므로 L과 R의 자릿수가 같다면, 앞에서 부터 탐색하며 L과 R의 해당 자릿수가 8로 같을때를 찾아주면된다.

 

예제의 경우 8808 8880 은 천의자리수와 백의자리수가 모두 8로 같아서 최소한으로 나올수있는 8의 갯수는 2개가 된다.

(만들수있는수는 88xx가 되어야하므로..)

 

이런식으로 코드를 짰다가 2번틀려서 반례를 찾았는데

 

8181 8282

답 = 1

출력 = 2

이다.

 

내코드는 천의 자리와 십의자리가 8로 같으므로 2개가 최소라 했는데, 만들수있는 수는 (81xx, 82xx)이런식으로 만들수있어서 답은 1이다.

반복문을 돌리는 과정에서 R[i]와 L[i]가 다르면, break해주는 조건문을 걸어줬고 맞았다.

 

소스코드

 

https://github.com/devxb/JJUNalgo/blob/master/1105%20%ED%8C%94/main.cpp

devxb/JJUNalgo