1941번: 소문난 칠공주

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


$O(1)$

25칸 중 7개의 칸을 선택해서 모두 인접해 있고 S가 4개 이상인 경우를 카운트

#include<cstdio>
#include<algorithm>
using namespace std;
char a[5][6];
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int r, vis[5][5], p[25], s, tot;
void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= 5 || y >= 5 || vis[x][y] || !p[x * 5 + y]) return;
    vis[x][y] = 1;
    s += a[x][y] == 'S';
    tot++;
    for (int i = 0; i < 4; i++) dfs(x + fx[i], y + fy[i]);
}
int main() {
    for (int i = 0; i < 5; i++) scanf("%s", a[i]);
    for (int i = 18; i < 25; i++) p[i] = 1;
    do {
        fill(vis[0], vis[5], 0);
        int i = s = tot = 0;
        for (; !p[i]; i++);
        dfs(i / 5, i % 5);
        r += tot == 7 && s > 3;
    } while (next_permutation(p, p + 25));
    printf("%d", r);
    return 0;
}

1759번: 암호 만들기

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


$O(c∗2^c)$

모든 경우를 조사한다.

#include<cstdio>
#include<algorithm>
int l, c;
char s[15], r[16];
int main() {
    scanf("%d %d", &l, &c);
    for (int i = 0; i < c; i++) scanf(" %c", &s[i]);
    std::sort(s, s + c);
    for (int i = 1 << c; --i;) {
        int p = 0, q = 0;
        for (int j = 0; j < c; j++) if (i & 1 << c - 1 - j)
            r[p++] = s[j], q += s[j] == 'a' || s[j] == 'e' || s[j] == 'i' || s[j] == 'o' || s[j] == 'u';
        if (p == l && q && p - q>1) r[l] = 0, puts(r);
    }
    return 0;
}

13134번: Baseball Watching

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


$O(?)$

9회까지 선생님이 취할 수 있는 이동 가지수는 3^9이다.
각 경우마다 선생님을 한 번도 만나지 않을 방법 2^9가지를 모두 조사한다.

#include<cstdio>
int n, c[19683], mini = 1e9, maxi;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int t = 0;
        for (int j = 0, x; j < 9; j++) scanf("%d", &x), t = t * 3 + x - 1;
        c[t]++;
    }
    for (int i = 0; i < 19683; i++) {
        int s = 0;
        for (int j = 0; j < 1 << 9; j++) {
            int t = 0;
            for (int k = 0, ti = i, tj = j; k < 9; k++, ti /= 3, tj /= 2) t = t * 3 + (ti % 3 + tj % 2) % 3;
            s += c[t];
        }
        if (mini > s) mini = s;
        if (maxi < s) maxi = s;
    }
    printf("%d %d", mini, maxi);
    return 0;
}

10597번: 순열장난

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


O(...) 대략 (n/2)C9

n을 정하고 모든 경우를 조사

#include<cstdio>
#include<cstdlib>
#include<cstring>
char s[92];
int len, n, r[50], ck[51];
void f(int h, int p, int x) {
    if (p == n) {
        for (int i = 0; i < n; i++) printf("%d ", r[i]);
        exit(0);
    }
    x = x * 10 + s[h] - '0';
    if (!x || x > n) return;
    if (!ck[x]) {
        ck[x] = 1;
        r[p] = x;
        f(h + 1, p + 1, 0);
        ck[x] = 0;
    }
    f(h + 1, p, x);
}
int main() {
    scanf("%s", s);
    len = strlen(s);
    n = len < 10 ? len : 9 + (len - 9) / 2;
    f(0, 0, 0);
    return 0;
}

5520번: The Clocks

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


$O(n*M*4^n)$ // n: 스위치 개수, M: 영향을 주는 시계의 최대 개수

모든 경우를 조사한다.

#include<cstdio>
const int f[][5] = { { 0,1,3,4 },{ 0,1,2 },{ 1,2,4,5 },{ 0,3,6 },{ 1,3,4,5,7 },{ 2,5,8 },{ 3,4,6,7 },{ 6,7,8 },{ 4,5,7,8 } }, c[] = { 4,3,4,3,5,3,4,3,4 };
int g[9], r = 1e9, p;
int main() {
    for (int i = 0; i < 9; i++) scanf("%d", g + i);
    for (int i = 1 << 18; i--;) {
        int t[9] = {}, s = 0, j;
        for (j = 0; j < 9; j++)
            for (int k = 0; k < c[j]; k++) t[f[j][k]] = (t[f[j][k]] + (i >> j * 2) * 3) % 4, s += (i >> j * 2) % 4;
        for (j = 0; j < 9; j++) if (g[j] ^ t[j]) break;
        if (j == 9 && r > s) r = s, p = i;
    }
    for (int i = 0; i < 9; i++) for (int k = (p >> i * 2) % 4; k--;) printf("%d ", i + 1);
    return 0;
}

1029번: 그림 교환

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


$O(n*2^n)$

모든 (그림을 소유했던 사람 집합, 마지막에 그림을 소유한 사람, 마지막 가격) 쌍이 노드로 존재하는 그래프를 탐색한다.

#include<cstdio>
int n, a[15][15], ck[1 << 15][15][10], r;
void f(int x, int y, int z, int c) {
    if (c > r) r = c;
    ck[x][y][z] = 1;
    for (int i = 0; i < n; i++) if (a[y][i] >= z&&!(1 << i&x) && !ck[1 << i | x][i][a[y][i]]) f(1 << i | x, i, a[y][i], c + 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%1d", &a[i][j]);
    f(1, 0, 0, 1);
    printf("%d", r);
    return 0;
}

1025번: 정사각형 찾기

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


$O(nm(n+m))$

가능한 모든 경우를 조사

#include<cstdio>
#include<cmath>
int n, m, a[9][9], r = -1;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) scanf("%1d", &a[i][j]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = -n; k < n; k++) {
                for (int l = -m; l < m; l++) {
                    int s = 0, x = i, y = j;
                    do {
                        s = s * 10 + a[x][y];
                        if (sqrt(s)*(int)sqrt(s) == s && r < s) r = s;
                        x += k;
                        y += l;
                    } while (x >= 0 & y >= 0 && x < n&&y < m && (k | l));
                }
            }
        }
    }
    printf("%d", r);
    return 0;
}

1093번: 스티커 수집

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


$O(n2^{n/2})$

knapsack problem을 O(n2^(n/2))에 푸는 방법이 있다.
(https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle)
이를 이용해 가치를 k 이상 얻기 위해 써야하는 최소 비용 r을 구할 수 있다.
처음 가지고 있는 스티커를 돈으로 환산하여 합한 값이 s라 하면
답은 max(r-s,0)이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, v[32], c[32], k, s, cnt[2] = { 1,1 }, r = 1e9;
pair<int, int> p[2][1 << 16];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", c + i);
    for (int i = 0; i < n; i++) scanf("%d", v + i);
    scanf("%d%d", &k, &m);
    for (int i = 0, x; i < m; i++) {
        scanf("%d", &x);
        s += c[x];
    }
    for (int i = 0; i < n; i++) {
        int h = i >= n / 2;
        for (int j = 0; j < cnt[h]; j++) p[h][j + cnt[h]] = { p[h][j].first + v[i],p[h][j].second + c[i] };
        cnt[h] *= 2;
    }
    sort(p[1], p[1] + cnt[1]);
    for (int j = cnt[1] - 1; j--;) p[1][j].second = min(p[1][j].second, p[1][j + 1].second);
    for (int i = 0; i < cnt[0]; i++) {
        int lb = lower_bound(p[1], p[1] + cnt[1], make_pair(k - p[0][i].first, 0)) - p[1];
        if (lb < cnt[1]) r = min(r, p[0][i].second + p[1][lb].second);
    }
    printf("%d", r < 1e9 ? max(r - s, 0) : -1);
    return 0;
}

13421번: 국민 랜드

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


"국민 랜드는 한 변의 길이가 1 이상인 정사각형......


$O(1)$

정사각형 길이가 2s 이라면 네 꼭지점 좌표는 (-s,-s), (-s,s), (s,-s), (s,s)가 된다.
기존의 네 점 (ai,bi)를 위 네 점과 대응시키는 4!의 경우가 존재한다.
모든 경우에 대해 가장 작은 비용의 최대 크기 정사각형을 찾자.
대응 관계가 정해졌을 때 s관한 비용의 함수 f(s)는

|-s-a1|+|-s-b1|+
|-s-a2|+|s-b2|+
|s-a3|+|-s-b3|+
|s-a4|+|s-b4|
가 되며 s=(A={-a1,-b1,-a2,b2,a3,-b3,a4,b4}의 중앙값) 일 때 함숫값이 최소가 된다.
최소 비용 중 최대 크기 정사각형을 구해야 하므로 정렬한 A의 원소 중 5번째 값을 s의 후보로 놓는다.
s가 음수가 될 수도 있는데 -s도 존재하므로 최소 비용 상의 최대 s값을 취하면 상관없다.
답은 2s이다.

네 점이 모두 원점에 있을 경우 s=0이 나올 것이다. 이 때는 문제 조건에 따라 1을 출력한다.

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[4];
long long mini = 8e9;
int r, a[8];
int main() {
    for (int i = 0; i<4; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(p, p + 4);
    do {
        for (int i = 0; i < 4; i++)
            a[i] = p[i].first*(1 - i / 2 % 2 * 2),
            a[i + 4] = p[i].second*(1 - i % 2 * 2);
        sort(a, a + 8);
        long long s = 0;
        for (int i = 0; i < 8; i++) s += abs(a[i] - a[4]);
        if (s<mini || s == mini&&a[4]>r) mini = s, r = a[4];
    } while (next_permutation(p, p + 4));
    printf("%d", max(r * 2, 1));
    return 0;
}

9663번: N-Queen

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


$O(n^2*n!)$

완전 탐색을 하되 행, 열, 두 방향의 대각선의 퀸 존재여부를 확인하여 탐색 시간을 줄인다.

#include<cstdio>
int ck[3][27], n, r;
void f(int h) {
    if (h == n) {
        r++;
        return;
    }
    for (int i = 0; i < n; i++) if (!ck[0][i] & !ck[1][h + i] & !ck[2][h - i + n - 1]) {
        ck[0][i] = ck[1][h + i] = ck[2][h - i + n - 1] = 1;
        f(h + 1);
        ck[0][i] = ck[1][h + i] = ck[2][h - i + n - 1] = 0;
    }
}
int main() {
    scanf("%d", &n);
    f(0);
    printf("%d", r);
    return 0;
}

13140번: Hello World!

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


$O(...)$

#include<cstdio>
#include<algorithm>
int n, a[10];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < 10; i++)a[i] = i;
    do {
        int p = a[2] * 1e4 + a[1] * 1e3 + a[3] * 110 + a[4];
        if (a[2] && a[6] && p + a[6] * 1e4 + a[4] * 1e3 + a[5] * 1e2 + a[3] * 10 + a[0] == n) {
            printf("  %d\n+ %d\n-------\n %6d", p, n - p, n);
            return 0;
        }
    } while (std::next_permutation(a, a + 10));
    puts("No Answer");
    return 0;
}

10974번: 모든 순열

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


$O(n*n!)$

#include<algorithm>
int a[8], n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) a[i] = i + 1;
    do {
        for (int i = 0; i < n; i++) printf("%d ", a[i]);
        puts("");
    } while (std::next_permutation(a, a + n));
    return 0;
}

1987번: 알파벳

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


$O(4^w)$ // w는 min(26,r*c)

dfs 탐색을 이용해서 모든 경로를 조사한다.

#include<cstdio>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int ck[99], n, m, r;
char s[20][20];
void f(int x, int y, int z) {
    if (x < 0 || y < 0 || x >= n || y >= m || ck[s[x][y]]) return;
    r = r>z ? r : z;
    ck[s[x][y]] = 1;
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i], z + 1);
    ck[s[x][y]] = 0;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    f(0, 0, 1);
    printf("%d", r);
    return 0;
}

1007번: Vector Matching

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


$O(tn{n \choose n/2})$

n/2개의 백터합을 풀어 쓰면 n/2개의 좌표는 더하고 n/2개의 좌표는 빼야 함을 알 수 있다.
모든 경우를 따져서 최소의 벡터 크기를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 20;
bool b[MAX_N];
int n, t, x[MAX_N], y[MAX_N];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d %d", x + i, y + i);
        for (int i = 0; i < n / 2; i++) b[i] = 0, b[i + n / 2] = 1;
        double r = 1e15, sx, sy;
        do {
            sx = sy = 0;
            for (int i = 0; i < n; i++) sx += (1 - b[i] * 2)*x[i], sy += (1 - b[i] * 2)*y[i];
            r = min(r, sqrt(sx*sx + sy*sy));
        } while (next_permutation(b, b + n));
        printf("%lf\n", r);
    }
    return 0;
}

10819번: 차이를 최대로

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


$O(n*n!)$


모든 경우를 조사하여 푼다. next_permutation 함수를 쓰면 쉽게 구현할 수 있다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, a[8], maxi, tot;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    do {
        tot = 0;
        for (int i = 0; i < n - 1; i++) tot += abs(a[i] - a[i + 1]);
        maxi = max(maxi, tot);
    } while (next_permutation(a, a + n));
    printf("%d", maxi);
    return 0;
}

$O(n\lg n)$


이 문제는 완전 검색을 할 필요가 없다. n개의 수열을 오름차순 정렬한 수열이 있다고 하자.

i) n이 짝수
m=n/2
작은 것 m개 a1<a2<...<am
큰 것 b1>b2>...>bm이 있다하자.
a1 b1 a2 b2 ...... am bm 과 같이 배열하면 최대이다.

ii)n이 홀수
m=(n-1)/2
작은 것 m개 a1<a2< ... < am
큰 것 m개 b1>b2> ... > bm
중앙값 c가 있다고 하자.

다음 두 배치 중 최댓값을 출력하면 된다.

am-1 b1 a1 b2 a2 ...... bm-1 am-1 bm c
bm a1 b1 a2 b2 ...... am-1 bm-1 am c

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, a[9];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    if (n % 2) printf("%d", 2 * a[n] - min(3 * a[n / 2] + a[n / 2 + 2], 3 * a[n / 2 + 1] + a[n / 2 - 1]));
    else printf("%d", 2 * a[n] - 2 * a[n / 2] - a[n / 2 + 1] - a[n / 2 - 1]);
    return 0;
}