1105 팔 / c++ / Silver1 / 12분
문제 및 코드
풀이 과정
그리디 / 수학
- 20억 이하의 자연수 L과 L보다 큰 20억 이하의 자연수 R 사이의 수 중, 8이 가장 적게 들어간 수의 8의 개수를 출력하는 문제
- ‘없앨 수 있는 8’과 ‘없앨 수 없는 8’을 나눠보려고 생각했다.
- 수의 범위라고 하더라도 8888 부터 8899 까지면, 뒤의 두자리인 88 ~ 99는 조절이 가능하더라도, 앞의 두자리 88은 무조건 들어갈 수 밖에 없다.
- 이 경우 없앨 수 없는 8은 앞의 두자리 8이고, 없앨 수 있는 8은 뒤의 두자리 8이다.
- 즉, L과 R를 앞에서부터 비교했을 때, 공통적으로 등장하는 수는 조절이 불가능한 수이고, 그 수들 중 등장하는 8의 개수가 없앨 수 없는 8의 수, 즉 정답인 것이다.
- L과 R의 각 자리수를 비교하기 위해 string 으로 변환해줬고, 자리수가 맞지 않는 경우를 대비해서 R의 자리수 - L의 자리수 만큼의 ‘0’을 L의 string 에 추가해서 비교해줬다.
- 비교시 해당 자리의 수가 맞지 않는 시점에서 해당 수는 조절 가능한 수가 되어버리므로 비교 종료
- 아니라면 해당 자리의 수가 8인지 여부에 따라 Answer 증가 후 다음 자리로 이동을 반복
- 비교 종료 후 Answer을 출력
- 해결
회고
- 어떻게 8을 최소화 할 수 있을까에서, 어떻게 주어진 8을 지울 수 있을까로, 다음엔 어떤 8을 지울 수 없을까로 생각이 이어져서, 앞자리부터 공통된 수는 바꿀 수 없고, 그 수들 중 8의 개수가 정답이다 라는 로직을 발견할 수 있었다.
- 풀 때까지도 긴가민가 했지만, 다행히 내가 생각한 로직이 맞았던 것 같다. 간만에 재미있는 문제였다.
