[백준/C++] 24268번 2022는 무엇이 특별할까?

---

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


int main()
{
    int year, bits, value;
    cin >> year >> bits ;

    vector<int> arr(bits);
    iota(arr.begin(), arr.end(), 0) ;
    
    while(next_permutation(arr.begin(), arr.end()))
    {
        if(arr[0] == 0) continue;
        value = 0;

        for(int i = 0 ; i < arr.size() ; i++)
        {
            value += arr[arr.size() - i - 1] * pow(bits, i);
        }

        if(value > year)
        {
            cout << value << "\n";
            return 0;
        }
    }
    cout << "-1\n" ;
    return 0;
}

---

처음에 그냥 주어진 수부터 1씩 늘려가며 조건(N진수에서 0~ N-1까지 수가 나타나는 것)을 만족하는 수를 계속 찾도록 하였는데 시간 초과가 계속해서 떠서 연도를 늘려가는 것보다 주어진 진수 내에서 가능한 모든 조합을 비교해보는 것이 좋겠다고 생각하게 되었습니다.

 

그런데 조합을 계속해서 바꿔나가는 것을 코드로 구현할 줄 몰라서 찾아보다가 next_permutation 이라는 함수를 알게 되었고 이 함수는 간략하게 설명하면 계속해서 오름차순으로 다음 조합을 던져줍니다. 그러다 더 이상 조합이 없게되면 false를 리턴하게 됩니다.

 

그리고 iota 라는 함수도 새롭게 알게 되었는데 for문을 사용해서 배열의 특정 구간에 숫자를 1개씩 증가하도록 하는 것과 같습니다.

즉 iota(arr.begin(), arr.end(), 0) == for(int i = 0; i < arr.size() ; i++) arr[i] = i 라는 것입니다.

참고 레퍼런스: https://en.cppreference.com/w/cpp/algorithm/iota

 

이번 문제에서 추가적인 테스트 케이스로 사용한 것들은 3가지입니다. year를 늘리는 방식에서는 1 9를 입력하였을 때 결과를 출력하는데 4초 이상걸렸고 이게 시간 초과의 원인이 아니였을까합니다.

1   9	44317196
100   3	-1
2   2	-1

 

---

문제: https://www.acmicpc.net/problem/24268

24268번: 2022는 무엇이 특별할까?