엘리스 코드 챌린지 Day 7

code-challenge.elice.io

 

Day 6 문제는 밤 11시 30분 정도에 접속해서 본 다음 열심히 고민했는데 풀지 못했고.. 적당한 전략으로 60점 정도의 부분 점수를 긁었습니다. Day 7부터는 긴장을 늦추지 말고 일찍 확인해야겠습니다!

 

엘리스 코드 챌린지 Day 7에는 '계기판 조작하기'라는 문제가 나왔습니다.

Day 7 문제를 보고 저는 우선 digit DP를 떠올려 보았습니다.

 

하지만 digit DP를 짜는 것이 번거롭기 때문에, 다른 방법이 있는지 좀 더 고민해보았습니다.

그런데 그냥 näive한 방법이 통과할 것 같아서 그렇게 풀어 맞췄습니다.

 

방법은 그냥 '자연수 $i$의 모든 자릿수의 종류가 정확히 $K$일 때까지 $i$를 늘리며 반복'입니다.

최악의 경우는 $N=10^7$인 경우인데, 이때 $K>7$이라면 답이 유일하게 결정된다는 점을 이용해 탐색할 $i$의 개수를 줄일 수 있습니다.

또한 $K>7$일 경우 일반적으로 답이 유일합니다.

 

그 외에는 자릿수를 볼 때 cnt 배열 따위를 만들지 않고, 비트마스킹을 이용하여 상수를 낮췄습니다. 혹시 모를 GCC 최적화도 넣었으나, 없어도 상관은 없는 것 같습니다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    if (k == 10) {
        cout << "1023456789";
    } else if (k == 9) {
        cout << "102345678";
    } else if (k == 8) {
        cout << "10234567";
    } else {
        // n <= 7
        for (int i=n; ; ++i) {
            int j = i, f = 0;
            while (j) f |= 1<<(j%10), j /= 10;
            if (__builtin_popcount(f) == k) {
                cout << i;
                return 0;
            }
        }
    }
}