[BOJ] 백준 2659 십자카드 문제 (KOI 1997 초등부)

문제 링크

www.acmicpc.net/problem/2659

2659번: 십자카드 문제

 

풀이

가능한 모든 네 자리 수의 조합을 찾고, 4번씩 돌려서 시계수를 찾은 다음 중복을 제거해줍니다.

입력으로 들어온 시계수가 몇 번째로 작은 수인지 lower bound를 이용해 구해주면 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
using namespace std;

vector<int> p;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    for (int i = 1; i < 10; i++) {
        for (int j = 1; j < 10; j++) {
            for (int k = 1; k < 10; k++) {
                for (int w = 1; w < 10; w++) {
                    int t[8] = {i, j, k, w, i, j, k, w};
                    int mini = 999'999;
                    for (int x = 0; x < 4; x++) {
                        int num = 0;
                        for (int y = 0; y < 4; y++) {
                            num *= 10;
                            num += t[x + y];
                        }
                        mini = min(mini, num);
                    }
                    p.push_back(mini);
                }
            }
        }
    }
    sort(all(p));
    p.erase(unique(all(p)), p.end());
    int ans = 999'999;
    int t[8] = {a, b, c, d, a, b, c, d};
    for (int i = 0; i < 4; i++) {
        int num = 0;
        for (int j = 0; j < 4; j++) {
            num *= 10;
            num += t[i + j];
        }
        ans = min(ans, (int) (upper_bound(all(p), num) - p.begin()));
    }
    cout << ans;
}