Problem F1, F2 풀이 (C++)

 문제 링크 F1 : https://codeforces.com/contest/1560/problem/F1

              F2: https://codeforces.com/contest/1560/problem/F2

문제 F1과 F2의 차이는 k의 범위이기 때문에 F2를 풀면 F1까지 풀린다.

풀이 과정은 다음 과정을 반복한다.


1. n이 k-beautiful 인지 확인하여 맞는다면 n을 출력하고 아니라면 2번 과정을 진행한다.

2. n의 가장 높은 자리부터 순회하면서 숫자의 종류가 k + 1개가 되는 순간의 위치를 확인한다.

   해당 숫자가 9가 아니라면 해당 숫자를 +1 하고 4번 과정을 진행한다.

   해당 숫자가 9라면 3번 과정을 진행한다.

3. 숫자 9가 아닐 때까지 한자리씩 올라간다. 숫자 9가 아닌 수가 나올 경우 해당 숫자를

   +1 하고 4번 과정을 진행한다.

4. +1한 숫자의 위치보다 낮은 자리의 수들을 모두 0으로 정한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <set>
 
using namespace std;
 
bool checkBeautiful(string n, int k) {
 
    set<char> s;
 
    for (char ch : n)
        s.insert(ch);
 
    if (s.size() <= k)
        return true;
    else
        return false;
}
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        string n;
        int k;
        cin >> n >> k;
 
        while (true) {
 
            if (checkBeautiful(n, k) == true) {
                cout << n << endl;
                break;
            }
 
            set<char> s;
 
            for (int i = 0; i < n.length(); i++) {
 
                s.insert(n[i]);
 
                if (s.size() > k) {
                    
                    int pos = i;
 
                    while (n[pos] == '9')
                        pos--;
 
                    n[pos] += 1;
                    for (int j = pos + 1; j < n.length(); j++)
                        n[j] = '0';
 
                    break;
                }
            }
        }
 
    }
 
    return 0;
}
cs

댓글

댓글 쓰기