류나의 작은 DB

27살 류나의 바르고 다르게 살기

Programming/Algorithms

UCPC 2022 예선 D-20~D-17 문제풀이 일지

Ryuna (류준범) 2022. 6. 15. 23:06

6월 12, 13, 14일을 설렁설렁 보내다가 15일이 되어 정신이 든 나...

늦었다고 생각할 때가 가장 빠른 때라고 하니 달려보겠습니다.

목차

1. 알고리즘 진도

- 2750번: 수 정렬하기

- 10815번: 숫자 카드

- 14425번: 문자열 집합

- 1269번: 대칭 차집합

- 11478번: 서로 다른 부분 문자열의 개수

- 3009번: 네 번째 점

- 2477번: 참외밭

- 3053번: 택시 기하학

- 1002번: 터렛

- 1004번: 어린 왕자

- 1358번: 하키

- 5086번: 배수와 약수

- 1037번: 약수

- 1934번: 최소공배수

- 2981번: 검문

- 3036번: 링

- 1010번: 다리 놓기

- 2004번: 조합 0의 개수

- 15651번: N과 M (3)

- 2580번: 스도쿠

- 14888번: 연산자 끼워넣기

- 14889번: 스타트와 링크


알고리즘 진도

최근 2주 정도 웹 개발하느라 알고리즘 문제풀이를 소홀히 했기 때문에 'BOJ 단계별로 풀어보기' 초반부의 풀지 않았던 문제를 풀어보면서 감을 되찾는 과정을 시행하기로 했습니다.

이에 따라 11일에 6~10단계를 완료했고, 이번에는 15단계 정도까지 완료할 생각으로 임했습니다.

※ C++ 코드 템플릿

혹시 제 코드를 참고하실 분들은 코드 최상단에 아래의 코드를 붙여넣어 주세요.

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define forn(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define all(v) (v).begin(), (v).end()

2750번: 수 정렬하기

https://www.acmicpc.net/problem/2750

 

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

문제의 의도는 시간 복잡도가 O(n²)인 정렬 알고리즘로 풀어봐라! 인 것 같기에 내장 sort 함수를 쓰지 않고 풀어보기로 했습니다.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    vector<int> A(N);
    forn(i, 0, N-1) cin >> A[i];

    forn(i, 0, N-1) {
        forn(i, 0, N-2) {
            if (A[i] > A[i+1]) swap(A[i], A[i+1]);
        }
    }

    forn(i, 0, N-1) cout << A[i] << "\n";

    return 0;
}

알고리즘 분류: 구현, 정렬

현 시점 난이도: 브론즈 II

10815번: 숫자 카드

https://www.acmicpc.net/problem/10815

 

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

쓰기 편한 ordered 자료구조(집합 등)를 사용하면 시간제한 안에 될 것 같습니다.

 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    set<int> card; // an ordered set - insert O(logn)
    forn(i, 0, N-1) {
        int c;
        cin >> c;
        card.insert(c);
    }

    int M;
    cin >> M;
    forn(i, 0, M-1) {
        int q;
        cin >> q;
        if (card.find(q) != card.end()) // find O(logn)
            cout << "1 ";
        else
            cout << "0 ";
    }

    return 0;
}

알고리즘 분류: 자료 구조, 정렬, 이분 탐색

현 시점 난이도: 실버 V

14425번: 문자열 집합

https://www.acmicpc.net/problem/14425

 

14425번: 문자열 집합

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.  다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어

www.acmicpc.net

역시 집합을 사용하는데, 문자열을 받아야 합니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    set<string> S;
    forn(i, 0, N-1) {
        string str;
        cin >> str;
        S.insert(str);
    }
    int ans = 0;
    forn(i, 0, M-1) {
        string q;
        cin >> q;
        if (S.find(q) != S.end()) ++ans;
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 자료 구조, 문자열, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

현 시점 난이도: 실버 III

1269번: 대칭 차집합

https://www.acmicpc.net/problem/1269

 

1269번: 대칭 차집합

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어

www.acmicpc.net

Python에 대칭 차집합이 구현되어 있는 것을 알고 있어서, 이를 사용했습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

A = set(map(int, input().rstrip().split()))
B = set(map(int, input().rstrip().split()))
C = A.symmetric_difference(B)

print(len(C))

알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

현 시점 난이도: 실버 III

11478번: 서로 다른 부분 문자열의 개수

https://www.acmicpc.net/problem/11478

 

11478번: 서로 다른 부분 문자열의 개수

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

www.acmicpc.net

C++의 substr 또는 Python의 문자열 슬라이스, 그리고 집합 자료구조를 이용하면 간단합니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;
    int N = S.size();
    set<string> substring;
    forn(i, 0, N-1) {
        forn(j, 1, N-i) {
            substring.insert(S.substr(i, j));
        }
    }
    cout << substring.size();

    return 0;
}

알고리즘 분류: 자료 구조, 문자열, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

현 시점 난이도: 실버 III

3009번: 네 번째 점

https://www.acmicpc.net/problem/3009

 

3009번: 네 번째 점

세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.

www.acmicpc.net

축에 평행한 직사각형이 문제의 조건이니까, x 방향과 y 방향 각각 두번씩 나온 숫자 하나와 한번 나온 숫자 하나가 있게 됩니다.

그러니 한 번만 나온 숫자를 출력하면 되겠죠.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> X(3), Y(3);
    forn(i, 0, 2) cin >> X[i] >> Y[i];
    sort(all(X));
    sort(all(Y));
    if (X[0] == X[1]) cout << X[2] << " ";
    else cout << X[0] << " ";
    if (Y[0] == Y[1]) cout << Y[2];
    else cout << Y[0];

    return 0;
}

알고리즘 분류: 구현, 기하학

현 시점 난이도: 브론즈 III

2477번: 참외밭

https://www.acmicpc.net/problem/2477

 

2477번: 참외밭

첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지

www.acmicpc.net

올바른 방향만 찾으면 계산이 쉽지만, 그 방향을 찾는 것이 까다롭습니다.

저는 반시계방향으로 이동한다는 것에서 아이디어를 얻어, 예제 입력과 동일한 크기 순서가 아니라면 주어진 입력의 순서를 돌려버렸습니다.

이를 위해 벡터가 아닌 덱을 사용했구요.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int K;
    cin >> K;
    deque<pii> L(6);
    forn(i, 0, 5) cin >> L[i].F >> L[i].S;
    while (L[0].S < L[2].S || L[0].S < L[4].S
        || L[1].S < L[3].S || L[1].S < L[5].S) {
        pii front = L[0];
        L.pop_front();
        L.PB(front);
    }
    cout << K * (L[0].S * L[1].S - L[3].S * L[4].S);

    return 0;
}

알고리즘 분류: 구현, 기하학

현 시점 난이도: 실버 III

3053번: 택시 기하학

https://www.acmicpc.net/problem/3053

 

3053번: 택시 기하학

첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다.

www.acmicpc.net

C++에서 파이 상수는 M_PI를 사용하면 됩니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int R;
    cin >> R;
    cout << fixed;
    cout.precision(6);
    cout << M_PI * R * R << "\n" << 2.00000000 * R * R;

    return 0;
}

알고리즘 분류: 수학, 기하학

현 시점 난이도: 브론즈 III

1002번: 터렛

https://www.acmicpc.net/problem/1002

 

1002번: 터렛

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

www.acmicpc.net

두 원의 교점의 개수를 구해야 하는데, 두 원의 중심 사이의 거리와 반지름 사이의 관계를 이용합니다.

경우의 수가 조금 많은 편입니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
        int cho_baik = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
        int ryu_plus = (r1 + r2) * (r1 + r2);
        int ryu_minus = (r1 - r2) * (r1 - r2);
        if (cho_baik == 0 && r1 == r2) cout << "-1\n";
        else if (cho_baik < ryu_minus) cout << "0\n";
        else if (cho_baik == ryu_minus) cout << "1\n";
        else if (cho_baik < ryu_plus) cout << "2\n";
        else if (cho_baik == ryu_plus) cout << "1\n";
        else cout << "0\n";
    }

    return 0;
}

알고리즘 분류: 수학, 기하학

현 시점 난이도: 실버 III

1004번: 어린 왕자

https://www.acmicpc.net/problem/1004

 

1004번: 어린 왕자

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주

www.acmicpc.net

출발점과 도착점이 각 행성계 내부 또는 외부에 있는지를 조사해서 서로 반대쪽에 있으면 답에 1을 더하는 식으로 풀면 되겠습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int n;
        cin >> n;
        int ans = 0;
        forn(i, 0, n-1) {
            int cx, cy, r;
            cin >> cx >> cy >> r;
            int start_c = (cx - x1) * (cx - x1) + (cy - y1) * (cy - y1);
            bool is_start_in = start_c < r * r;
            int end_c = (cx - x2) * (cx - x2) + (cy - y2) * (cy - y2);
            bool is_end_in = end_c < r * r;
            if (is_start_in != is_end_in) ++ans;
        }
        cout << ans << "\n";
    }

    return 0;
}

알고리즘 분류: 기하학

현 시점 난이도: 실버 III

1358번: 하키

https://www.acmicpc.net/problem/1358

 

1358번: 하키

첫째 줄에 수 W H X Y P가 주어진다. P는 선수의 수이다. W와 H는 100보다 작거나 같은 자연수이고, H는 짝수이다. X와 Y는 절댓값이 100보다 작거나 같은 정수이다. P는 최대 50인 자연수이다. 둘째 줄부

www.acmicpc.net

링크를 세 부분으로 나누고 각각에 대해 주어진 좌표를 포함하는지 계산하면 됩니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int W, H, X, Y, P;
    cin >> W >> H >> X >> Y >> P;
    int ans = 0;
    forn(i, 1, P) {
        int x, y;
        cin >> x >> y;
        if (x >= X && x <= X + W && y >= Y && y <= Y + H) ++ans;
        else {
            bool left = (x - X) * (x - X) + (y - Y - H/2) * (y - Y - H/2) <= (H * H) / 4;
            bool right = (x - X - W) * (x - X - W) + (y - Y - H/2) * (y - Y - H/2) <= (H * H) / 4;
            if (left || right) ++ans;
        }
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 기하학

현 시점 난이도: 실버 IV

5086번: 배수와 약수

https://www.acmicpc.net/problem/5086

 

5086번: 배수와 약수

각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다.

www.acmicpc.net

약수와 배수 관계 판정 문제!

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int A, B;
    cin >> A >> B;
    while (A || B) {
        if (A % B && !(B % A)) cout << "factor\n";
        else if (!(A % B) && B % A) cout << "multiple\n";
        else cout << "neither\n";
        cin >> A >> B;
    }

    return 0;
}

알고리즘 분류: 수학, 사칙연산

현 시점 난이도: 브론즈 III

1037번: 약수

https://www.acmicpc.net/problem/1037

 

1037번: 약수

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되

www.acmicpc.net

자신과 1을 제외한 약수가 주어졌을 때, 수를 구하는 방법은...?

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int num;
    cin >> num;
    vector<int> fac(num);
    forn(i, 0, num-1) cin >> fac[i];
    sort(all(fac));
    cout << fac[0] * fac[num-1];

    return 0;
}

알고리즘 분류: 수학, 정수론

현 시점 난이도: 브론즈 I

1934번: 최소공배수

https://www.acmicpc.net/problem/1934

 

1934번: 최소공배수

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있

www.acmicpc.net

최소공배수를 구하는 문제. 원래는 유클리드 호제법 등으로 약수를 다 구해야 하지만 lcm이라는 함수가 C++17에 있는데 굳이?

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int A, B;
        cin >> A >> B;
        cout << lcm(A, B) << "\n";
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 유클리드 호제법

현 시점 난이도: 브론즈 I

2981번: 검문

https://www.acmicpc.net/problem/2981

 

2981번: 검문

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간

www.acmicpc.net

이 문제를 풀려면 첫째, 가능한 M들의 공통 성질을 알아야 하고, 둘째, 그 성질을 만족하는 수들을 빠르게 구하는 방법을 알아야 합니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> num(N);
    forn(i, 0, N-1) {
        cin >> num[i];
    }
    sort(all(num));
    int g;
    forn(i, 0, N-2) {
        if (i == 0) g = num[1] - num[0];
        else g = gcd(g, num[i+1] - num[0]);
    }
    vector<int> M;
    forn(i, 2, g) {
        if (i * i > g) break;
        if (g % i == 0) M.PB(i);
    }
    int n = M.size();
    forn(i, 1, n) if (M[n-i] * M[n-i] != g) M.PB(g / M[n-i]);
    M.PB(g);
    n = M.size();
    forn(i, 0, n-1) cout << M[i] << " ";

    return 0;
}

알고리즘 분류: 수학, 정수론, 유클리드 호제법

현 시점 난이도: 골드 IV

3036번: 링

https://www.acmicpc.net/problem/3036

 

3036번: 링

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

www.acmicpc.net

기약분수 꼴로 나타내야 한다는 조건이 있는 문제입니다. 분자와 분모의 최대공약수를 구해야겠죠.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    int R;
    cin >> R;
    forn(i, 1, N-1) {
        int r;
        cin >> r;
        int g = gcd(r, R);
        cout << R / g << "/" << r / g << "\n";
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 유클리드 호제법

현 시점 난이도: 실버 IV

1010번: 다리 놓기

https://www.acmicpc.net/problem/1010

 

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

M개 중 N개를 순서 없이 고르는 경우의 수를 구하는 문제죠.

이항 계수 구하는 과정은 입력이 작아 재귀로도 될 것 같지만, 동적 계획법을 써 보았습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        vector<vector<int>> comb(M+1, vector<int>(M+1, 1));
        forn(i, 1, M) {
            forn(j, 1, i-1) {
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
            }
        }
        cout << comb[M][N] << "\n";
    }

    return 0;
}

알고리즘 분류: 수학, 다이나믹 프로그래밍, 조합론

현 시점 난이도: 실버 V

2004번: 조합 0의 개수

https://www.acmicpc.net/problem/2004

 

2004번: 조합 0의 개수

첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.

www.acmicpc.net

조합 계산 공식을 생각해 보면 팩토리얼에서 2와 5 인수의 개수를 3번씩 계산하면 됨을 알 수 있습니다.

int fac(int k, int l) {
    int ans = 0;
    while (k) {
        ans += k / l;
        k /= l;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int fives = fac(n, 5) - fac(m, 5) - fac(n-m, 5);
    int twos = fac(n, 2) - fac(m, 2) - fac(n-m, 2);
    cout << min(fives, twos);

    return 0;
}

알고리즘 분류: 수학, 정수론

현 시점 난이도: 실버 II

15651번: N과 M (3)

https://www.acmicpc.net/problem/15651

 

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

백트래킹 입문 문제 중 하나죠. N과 M 시리즈! 3번 문제의 경우는 숫자를 고르고 나서 골라진 여부를 bool로 저장할 필요가 없어서 체감 난이도가 낮습니다.

int N, M;
vector<int> seq;

void bt(int k) {
    if (k == M) {
        forn(i, 0, M-1) cout << seq[i] << " ";
        cout << "\n";
        return;
    }
    forn(i, 1, N) {
        seq.push_back(i);
        bt(k+1);
        seq.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    bt(0);

    return 0;
}

알고리즘 분류: 백트래킹

현 시점 난이도: 실버 III

2580번: 스도쿠

https://www.acmicpc.net/problem/2580

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

꽤 어려운 백트래킹 문제네요.

1. 백트래킹을 아무 순서로나 하면 시간 초과.

2. 숫자를 1부터 9까지 다 넣어보면서 올바른지 확인하면 시간 초과.

여기에 추가로 더 최적화가 필요할 수도 있을 것 같아요.

vector<vector<int>> board(9, vector<int>(9));
vector<pii> zero;
bool solved = false;

int valid_numbers(pii p) {
    // horizontal line
    int ans = (1 << 10) - 1;
    forn(i, 0, 8) {
        int num = board[p.F][i];
        ans &= ~(1 << num);
    }
    // vertical line
    forn(i, 0, 8) {
        int num = board[i][p.S];
        ans &= ~(1 << num);
    }
    // 3*3 box
    forn(i, 0, 2) {
        forn(j, 0, 2) {
            int num = board[p.F - p.F % 3 + i][p.S - p.S % 3 + j];
            ans &= ~(1 << num);
        }
    }
    return ans;
}

void solve(int k) {
    if (k == zero.size()) {
        forn(i, 0, 8) {
            forn(j, 0, 8) cout << board[i][j] << " ";
            cout << "\n";
        }
        solved = true;
        return;
    }
    int bitmask = valid_numbers(zero[k]);
    forn(n, 1, 9) {
        if (!(bitmask & (1 << n))) continue;
        board[zero[k].F][zero[k].S] = n;
        solve(k+1);
        if (solved) return;
        board[zero[k].F][zero[k].S] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    forn(i, 0, 8) {
        forn(j, 0, 8) {
            int n;
            cin >> n;
            board[i][j] = n;
            if (n == 0) zero.PB(MP(i, j));
        }
    }
    solve(0);

    return 0;
}

알고리즘 분류: 백트래킹

현 시점 난이도: 골드 IV

14888번: 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

단계별로 풀어보기 내에서는 뒤에 배치되어 있지만, N-Queen이나 스도쿠 문제보다 확연히 쉬운 문제라고 할 수 있습니다,

int N;
vector<int> A, op, eq;
int mx = -1e9;
int mn = 1e9;

void solve(int k) {
    if (k == N-1) {
        int ans = A[0];
        forn(i, 0, N-2) {
            if (eq[i] == 0) ans += A[i+1];
            if (eq[i] == 1) ans -= A[i+1];
            if (eq[i] == 2) ans *= A[i+1];
            if (eq[i] == 3) ans /= A[i+1];
        }
        mx = max(mx, ans);
        mn = min(mn, ans);
        return;
    }
    forn(i, 0, 3) {
        if (op[i] == 0) continue;
        --op[i];
        eq.push_back(i);
        solve(k+1);
        ++op[i];
        eq.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    forn(i, 0, N-1) {
        int a;
        cin >> a;
        A.PB(a);
    }
    forn(i, 0, 3) {
        int o;
        cin >> o;
        op.PB(o);
    }
    solve(0);
    cout << mx << "\n" << mn;

    return 0;
}

알고리즘 분류: 브루트포스 알고리즘, 백트래킹

현 시점 난이도: 실버 I

14889번: 스타트와 링크

https://www.acmicpc.net/problem/14889

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

스타트 팀과 링크 팀을 어떻게 반반씩 인원을 배정할지, 그리고 점수는 어떻게 매겨질지 생각해보면 풀리는 문제.

int N;
vector<vector<int>> S;
int team, chosen; // bitmask
int mn = 1e9;

void solve(int k) {
    if (k == N/2) {
        // construct both teams
        vector<int> start, link;
        forn(i, 0, N-1) {
            if (team & (1 << i)) start.PB(i);
            else link.PB(i);
        }
        // sum of start team
        int start_sum = 0;
        forn(i, 0, k-1) {
            forn(j, 0, k-1) {
                start_sum += S[start[i]][start[j]];
            }
        }
        // sum of link team
        int link_sum = 0;
        forn(i, 0, k-1) {
            forn(j, 0, k-1) {
                link_sum += S[link[i]][link[j]];
            }
        }
        mn = min(mn, abs(start_sum - link_sum));
        return;
    }
    forn(i, 0, N-1) {
        if (chosen & (1 << i)) continue;
        team |= (1 << i);
        forn(j, 0, i) chosen |= (1 << j);
        solve(k+1);
        team &= ~(1 << i);
        forn(j, i, N-1) chosen &= ~(1 << j);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    forn(i, 0, N-1) {
        vector<int> v;
        S.PB(v);
        forn(j, 0, N-1) {
            int s;
            cin >> s;
            S[i].PB(s);
        }
    }
    solve(0);
    cout << mn;

    return 0;
}

알고리즘 분류: 브루트포스 알고리즘, 백트래킹

현 시점 난이도: 실버 II

BOJ 랜덤 디펜스

...는 내일부터 꼭 다시 하겠습니다!!


아 갈 길이 멀구나.

1 2 3 4 5 6 7 8 9 ··· 35