[1105] 팔

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

1105번: 팔

그리디 문제다. 숫자가 아닌 문자열로 접근해서 풀었다. 숫자로 접근하게 된다면 최대 범위가 0 ~ 2,000,000,000 이므로 분명 시간 초과가 일어날 것이다. 따라서 8이 나올 수 있는가에 대한 조건만 생각해서 접근해야 한다.

 

우선 자릿수의 변동이 일어나면 8이 나올 수 없다. 즉 L과 R의 자릿수를 먼저 체크해야 하고, 이후 자릿수가 같다면 어느 자리까지 제한하였는지를 확인해야 한다. 각 자릿수의 숫자가 같을 경우에만 8의 개수를 세고 각 자릿수가 달라지는 시점이 온다면 해당 숫자는 8이 아닌 수로 바꿀 수 있다는 뜻으로 접근하면 된다.

 

풀이

자릿수가 다르다면 8이 없는 구간이 생길 수밖에 없으니 0을 출력하면 된다.

자릿수가 같다면 가장 큰 자릿수부터 숫자를 비교하여 8의 개수를 세면 되는데, 서로의 숫자가 다르다면 더 이상 숫자를 셀 필요 없다.

 

정답 코드