Codeforces Round #743 (Div. 2) - A. Countdown

문제 설명

당신은 $n$ 자리 정수를 나타낼 수 있는 전자 시계를 가지고 있다. 각 자리는 $0$부터 $9$까지 정수를 표현할 수 있다. 그래서 모든 시계는 $0$부터 $10^{n} - 1$까지의 수를 표현한다. 이 시계는 만약 숫자가 $10^{n - 1}$보다 작으면 $0$으로 시작할 수 있다.

당신은 가능한 한 지시사항을 적게 사용해서 시계에 0이 나타나게 하고 싶다. 지시사항은 다음과 같고, 한번에 하나씩 수행할 수 있다.

• 시계의 숫자를 $1$ 줄인다.
• 두 숫자의 자리를 바꾼다. (어떤 자리수의 숫자를 바꿀 수 있을지 선택할 수 있으며, 이 두 숫자는 인접하지 않아도 된다.)

당신의 목표는 위에 적힌 지시사항을 최소로 사용해서 시계가 $0$이 나타나게 하는 것이다.

Input
이 문제는 여러개의 테스트 케이스로 이루어져 있다. 첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 10^3)$

각 테스트케이스의 첫번째 줄에는 시계의 자릿수인 정수 $n$이 주어진다. $(1 \le n \le 100)$

각 테스트케이스의 두번째 줄에는 $n$자리로 이루어진 문자열이 주어진다. $s_{1}, s_{2}, ....., s_{n}(0 \le s_{1}, s_{2}, ....., s_{n} \le 9)$

주의사항: 이 시계는 만약 숫자가 $10^{n - 1}$보다 작으면 $0$으로 시작할 수 있다.

Output
각 테스트 케이스마다 시계에 0이 나타나게 하는 연산의 최소값을 출력한다.

Example
input
7
3
007
4
1000
5
00000
3
103
4
2020
9
123456789
30
001678294039710047203946100020

output
7
2
0
5
6
53
115

문제 접근

사용한 알고리즘: 그리디 알고리즘, 구현
걸린 시간 : 00:06
맨 뒷자리수에 있는 값을 1 줄이거나 각 자리수에 있는 숫자의 위치를 바꿔서 시계의 값이 000을 보여주게 하는것이 목표인 문제이다.
값을 1 줄이거나, 각 자리수의 위치를 바꾸는 총 2가지의 연산을 최소로 사용해야한다.
따라서 다음과 같이 생각하는게 좋을것 같다.

1. 맨 뒷자리수를 0으로 바꾼다.
2. 맨 뒷자리수가 0이면 0이 아닌 다른 자릿수와 맨 뒷자리수의 위치를 바꾼다.
3. 모든 자릿수가 0이 될때까지 1 ~ 2를 반복한다.

1번 과정은 맨 뒷 자리수가 나타나는 숫자만큼 값을 1 줄이는 연산을 하면 된다.
2번 과정은 0이 아닌 모든 자릿수를 찾아 그 수를 맨 뒤 0과 바꾸는 과정이고, 0이 아닌 자릿수의 개수만큼 이루어진다.

테스트케이스를 통해서 문제의 답이 도출되는 과정을 살펴보자.

• str = 2020인 경우
  1. 맨 뒤 자릿수가 0이기 때문에 1을 줄일 필요가 없다. (ans = 0, str = 2020)
  2. str[0]이 숫자가 2이기 때문에 맨 뒤자리수와 위치를 바꾼다. (ans += 1, str = 0022)
  3. 맨 뒤 자릿수가 2이기 때문에 1을 2번 줄인다. (ans += 2, str = 0020)
  4. str[2]이 숫자가 2이기 때문에 맨 뒤자리수와 위치를 바꾼다. (ans += 1, str = 0002)
  5. 맨 뒤 자릿수가 2이기 때문에 1을 두번 줄인다. (ans += 2, str = 0000)
  6. 모든 자릿수가 0이므로 과정을 종료한다. (ans = 0 + 1 + 2 + 1 + 2 == 6)
• str = 123456789인경우
  1. str[9]가 0이 아니기 때문에 str[o]번 1을 줄이는 연산을 해야한다. (ans += 9, str = 123456780)
  2. str[0]이 숫자가 0이 아니기 때문에 맨 뒤자리수와 위치를 바꾼다. (ans += 1, str = 023456781)
  3. str[9]가 0이 아니기 때문에 str[9]번 1을 줄이는 연산을 해야한다. (ans += 1, str = 023456780)
  4. str[1]이 숫자가 0이 아니기 때문에 맨 뒤자리수와 위치를 바꾼다. (ans += 1, str = 003456782)
     .
     .
     .
     .
     이 행위를 반복하면 답은 $1 * 8 + (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) = 53$가 된다.

정답 코드

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

int main(){
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        char arr[100];
        int ans = 0;
        for(int i = 0; i < n; i++) cin >> arr[i];
        for(int i = n - 1; i >= 0; i--){
            ans += (arr[i] - '0');
            if(i != n - 1 && arr[i] != '0') ans++;
        }
        cout << ans << "\n";
    }
}