문제
L과 R이 주어진다. 이 때, L보다 크거나 같고,
R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고,
R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 L보다 크거나 같고,
R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.
간단한거 같은데 처음에 많이 헷갈렸다.
8이 가장 적게 들어있는 수를 N 이라 하였을 때,
1 <= L <= N <= R <= 2,000,000,000
L, R이 자릿수가 틀리면 8의 갯수는 무조건 0이다.
L, R이 자릿수가 같을때, 높은 자리부터 L[i], R[i]모두 8일 경우에만(선택의 여지가 8밖에 없으므로)
8의 갯수가 하나 늘어나고, L[i] != R[i] 인 순간부터 개수를 찾을 필요가 없다.
왜냐하면 그 밑에 자리수에서 L[i] == R[i]라 하더라도 더 높은 자리수에서 숫자를 바꿀 수 있기 때문에
그 수를 선택할 필요가 없는거다.
이게 뭔가 설명하기가 어려운데 잘 생각해보면 그렇다.
이걸 처음에 생각하지 못해서 오답을 냈었다.
1808 2808 로 생각해보면
천의 자리수에서 값이 다르기 때문에 N = 2000 과 같은 8의 갯수가 0개인 숫자를 찾을 수 있다.
하지만 위의 관념을 이해 못하고 코드를 짜보면
천의 자리수는 둘이 같지 않으니 생략하고,
백의 자리에서 L과 R 모두 같은 숫자이고, 8이므로 8의 갯수가 하나 늘어나버린다!
라는 함정에 빠진다는거다.
헷갈리니 그냥 코드로 대신 나타내고 이 문제는 끝!
'Programming > ACMICPC' 카테고리의 다른 글
| ACMICPC 9494 데구르르 (0) | 2015.10.06 |
|---|---|
| ACMICPC 2168 타일 위의 대각선 (0) | 2015.10.05 |
| ACMICPC 9575 운 좋은 수 (0) | 2015.10.03 |
| ACMICPC 2869 달팽이는 올라가고 싶다 (0) | 2015.10.02 |
| ACMICPC 3029 경고 (0) | 2015.10.02 |