Codeforces Round #748 (Div. 3)-B. Make it Divisible by 25

문제 설명

양의 정수 $n$이 주어진다. 한번의 연산으로 아무 자릿수를 하나 선택한 다음 그 수를 제거할 수 있다. 즉, 숫자에서 임의의 자리를 선택하고 그 자리에 있는 수를 제거한다. 이 연산은 자릿수가 1개 남아있을 때는 수행할 수 없다. 만약 남아있는 수가 0으로 시작한다면 자동으로 0은 사라진다.

만약 숫자 $32925$ 가 있을 때, 3번째 자릿수를 지운다면 $3225$가 된다. 만약 숫자 $20099050$ 의 첫번째 자릿수를 지운다면 $99050$ 이 된다. (두개의 0이 자동으로 지워진다.)

$25$로 나누어 떨어지고 양수 로 만들기 위해서 필요한 최소 연산의 수는 몇개일까? 주어진 숫자에서 답은 항상 존재하고 주어진 숫자는 0으로 시작되지 않는것이 보장된다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 숫자 $n (25 \le n \le 10^{18})$ 이 주어진다. 주어진 숫자에서 답은 항상 존재하고 주어진 숫자는 0으로 시작되지 않는것이 보장된다.

Output
각 테스트케이스마다 $25$로 나누어 떨어지고 양수가 되기 위해서 필요한 최소 연산 수 인 $k$를 출력한다.

Example
input
5
100
71345
3259
50555
2050047

output
0
3
1
3
2

문제 접근

사용한 알고리즘: 그리디 알고리즘, 수학
걸린 시간 : 00:03
처음에 이 문제를 봤을 때 부끄럽게도 25의 배수 판정법을 몰라서 인터넷에 검색을 했다. 어떤 수가 25의 배수가 되려면 맨 뒷자리 두 수가 $00, 25, 50, 75$ 로 끝나야한다. 이것을 보자마자 나는 그리디 알고리즘을 사용하는 문제라는 것을 확신했고 문제 풀이에 들어갔다. 대회때에서는 코드를 예쁘게 짜는 것이 목적이 아니라 문제를 푸는 것이 목적이었기 때문에 그냥 for문을 4번써써 엄청 비효율적으로 풀었는데, 나중에 보니까 이 문제를 푸는 방법이 2가지가 있다는 것을 알수 있었다. 첫번째는 평범하지만 깔끔한 그리디 알고리즘을 써서 푸는법, 두번째는 고수들의 well-known 알고리즘을 사용해서 푸는 것이고 여기서는 두번째 방법을 소개하겠다.

결국 뒤에서 부터 주어진 두 수를 찾으면 앞에 어떤 수가 있더라도 상관이 없다는 것에 착안을 한 방법이다. 이중 for문을 이용해서 두 수가 $00, 25, 50, 75$ 이 수에 포함되는지 확인한다. 위치를 찾으면 첫번째 등장한 index 앞에 있는 수는 지울 필요가 없기 때문에 일단 전체 길이에서 $i$를 뺀다. 그리고 길이가 2인 수를 찾았기 때문에 마지막으로 2까지 뺀다. 여기서 왜 min()함수를 이용해서 최솟값을 확인안할까? 여기서 탐욕적 사고를 사용한 것 같다. 어짜피 뒤로 갈수록 앞에 지우지 않아도 될 수가 많아지기 때문에 자동으로 최솟값이 찾아지기 때문이다.

B번 문제를 조금 지저분하게 푼 것 같아서 레드-오렌지 코더들의 코드를 봤는데 전부다 이렇게 풀었다. 진짜 단 하나도 다른 방식으로 푼 사람을 본 적이 없어서 이런 well-known 코드를 자주 익혀서 더 효율적으로 코딩하고 싶다. 남들 다 아는건데 나만 모르면 조금 아쉽지 않을까?

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        int ans = 0;
        for(int i = 0; i < s.size(); i++){
            for(int j = i + 1; j < s.size(); j++){
                if(((s[i] - '0') * 10 + s[j] - '0') % 25 == 0) ans = s.size() - i - 2;
            }
        }
        cout << ans << "\n";
    }
}