Round 2는 두 시간동안 네 문제를 푸는 대회였군요..
이전 라운드에 비해 결과가 나오는데 시간이 좀 걸려서 4시까지 잠에 들지 못하는..
Round 3에 진출하는 커트라인은 20점에 페널티 1:37:36 이었군요. A를 완벽하게 풀고 Small 한 문제 풀면 되는 점수였네요.
통과하신 분들 모두 축하드려요 ~~

A. Cheating a Boolean Tree
[문제 설명]
이 문제에서는 Boolean Tree라고 부르는 Binary Tree를 하나 정의한다. Boolean Tree란 마지막 row만 제외하고는 모두 complete한 트리이며, 마지막 row에서도 왼쪽 노드에서부터 차례대로 채워져 있다. 또한 모든 노드의 Child 수는 0 또는 2이다.
이러한 Tree가 Boolean Tree라고 불리는 이유는 각 노드마다 0 또는 1의 값을 가지기 때문이다. 또한 interior node는 AND/OR 게이트를 포함한다. 어떤 노드가 AND 게이트를 가지고 있다면 두 개의 child node의 AND값을 갖게 되고, OR 게이트를 가지고 있다면 두 child node의 OR값을 갖게 되는 것이다.
우리는 이 트리의 root값에 흥미가 있다. Boolean Tree이기 때문에 당연히 root값도 0 또는 1일 것이다. 하지만 이 트리로부터 우리가 원하는 root값을 얻지 못할 수도 있다. 운좋게도, 당신에게는 Boolean Tree의 어떤 노드들은 AND/OR 게이트를 변경할 수 있다는 사실을 알고 있었다.
Boolean Tree의 정보와 변경 가능한 interior node의 정보가 입력으로 주어질 때, 최소한의 게이트 변경을 통하여 당신이 원하는 root값을 얻고자 한다. 만약 불가능하다면 IMPOSSIBLE을 출력한다.

[spoiler="풀이 보러가기..."] [문제 풀이]
모든 트리의 Leaf Node(End-Node)의 정보는 이미 주어져 있으므로 밑에서부터 하나씩 채워나가도록 하겠습니다. 제일 마지막 interior node(내부 노드)가 4번 이므로, 4번에서부터 차례대로 채워나가도록 하지요. 4번노드는 OR 게이트이며, 변경할 수 없는 노드입니다. 따라서 4번 노드의 값은 항상 1이라는 사실을 알 수 있지요. 4번 노드에 0이 채워질 수 있는 방법은 없습니다.
4번 노드의 모든 경우를 살펴보았으니 3번 노드를 봅시다. 3번 노드는 AND 게이트이며 게이트 변경이 가능합니다. 3번 노드에 0 값이 채워지기 위해서는 게이트 변경이 필요가 없지요. 따라서 3번 노드에 0이 오게 하려면 게이트 변경을 하지 않고도 가능하다는 것을 알 수 있습니다. 3번 노드에 1 값을 채우려면 OR 게이트로 변경해야 하지요? 따라서 3번 노드에 1이 오게 하려면 최소 1번의 게이트 변경이 필요하다는 것을 알 수 있습니다.
마찬가지로 2, 1번 노드에 대해서 같은 작업을 수행할 수 있습니다. 그러면 위의 트리에서는 1번만 바꿔주면 원하는 값(루트 노드의 값 = 1)을 얻을 수 있게 되지요. 시간복잡도 O(N)인 Dynamic Programming 이라고 볼 수 있겠습니다.[/spoiler]
[spoiler="소스코드 보러가기"]~~~ cpp

#include
using namespace std;
// table[i][j] = i번 노드가 j값을 가지기 위해 바꿔야 할 최소 게이트 수. (i = 1 ~ N, j = 0, 1)
int table[10005][2];
// g는 gate, c는 changable을 나타냅니다.
int g[10005], c[10005];
int T;
int M, V;
int main() {
scanf("%d", &T);
for (int cn = 1; cn <= T; ++cn) {
scanf("%d%d", &M, &V);
for (int i = 1; i <= M; ++i)
table[i][0] = table[i][1] = 999999;
for (int i = 1; i <= (M - 1) / 2; ++i)
scanf("%d%d", &g[i], &c[i]);
for (int i = (M + 1) / 2; i <= M; ++i) {
int num;
scanf("%d", &num);
table[i][num] = 0;
table[i][1 - num] = 999999;
}
for (int i = (M - 1) / 2; i >= 1; --i) {
int lc = i * 2, rc = i * 2 + 1;
if (g[i] == 0) { // OR
table[i][0] <?= table[lc][0] + table[rc][0];
table[i][1] <?= table[lc][0] + table[rc][1];
table[i][1] <?= table[lc][1] + table[rc][0];
table[i][1] <?= table[lc][1] + table[rc][1];
} else { // AND
table[i][0] <?= table[lc][0] + table[rc][0];
table[i][0] <?= table[lc][0] + table[rc][1];
table[i][0] <?= table[lc][1] + table[rc][0];
table[i][1] <?= table[lc][1] + table[rc][1];
}
if (c[i] == 1) { // 변경 가능한 노드라면,
if (g[i] == 0) { // OR게이트에서 AND게이트로 바꿉니다.
table[i][0] <?= table[lc][0] + table[rc][0] + 1;
table[i][0] <?= table[lc][0] + table[rc][1] + 1;
table[i][0] <?= table[lc][1] + table[rc][0] + 1;
table[i][1] <?= table[lc][1] + table[rc][1] + 1;
} else { // AND게이트에서 OR게이트로 바꿉니다.
table[i][0] <?= table[lc][0] + table[rc][0] + 1;
table[i][1] <?= table[lc][0] + table[rc][1] + 1;
table[i][1] <?= table[lc][1] + table[rc][0] + 1;
table[i][1] <?= table[lc][1] + table[rc][1] + 1;
}
}
}
printf("Case #%d: ", cn);
if (table[1][V] == 999999) printf("IMPOSSIBLE\n"); else printf("%d\n", table[1][V]);
}
}

[/spoiler]


 B. Triangle Areas
    [문제 설명]
  N * M 크기의 격자판이 주어져 있다. 이 격자판에 임의의 세 점을 잡아서 삼각형을 만들면, 그 넓이는 항상 .0 으로 끝나거나 .5로 끝난다는 사실을 알 수 있다. 
  0 <= x <= N, 0 <= y <= M 을 만족하는 세 점을 선택하여 우리는 A/2 의 넓이를 가지는 삼각형을 만들고 싶어한다. 즉, 입력으로 N, M, A가 주어졌을 때, 조건을 만족하는 삼각형의 세 꼭지점의 좌표를 출력하는 프로그램을 작성하시오. 만약 존재하지 않으면 IMPOSSIBLE을 출력한다.
[spoiler="풀이 보러가기..."]    [문제 풀이]
  프로그래밍 대회라고는 하지만, 꽤나 수학적인 문제입니다. 일단 임의의 세 점 (x1, y1), (x2, y2), (x3, y3)가 있을 때 삼각형의 넓이를 구하는 공식은 아래와 같습니다.
  area = | x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) | / 2
  어떤 삼각형이 있다고 가정하면, 우리는 그 삼각형을 평행이동하더라도 넓이가 변하지 않는다는 사실을 알고 있습니다. 또한 대칭이동을 해도 넓이는 변하지 않지요. 그렇다면 어떤 삼각형을 그리더라도, 한 점은 항상 원점에 오도록 옮길 수 있습니다. (자세한 증명은 생략합니다. 직접 몇 번 그려보시면 금방 아실 수 있을테니까요.)
  그러면 위의 식에서 x1 = 0, y1 = 0이 되므로 area = |x2 * y3 - x3 * y2| / 2 가 되지요. Small Dataset은 이 네 개의 변수를 가능한 모든 경우에 대해서 수행하면 답을 구할 수 있습니다.
  하지만 Large Dataset은 좌표의 범위가 크기 때문에 모든 경우를 다 살펴볼 수 없습니다. 따라서 약간의 변형이 필요합니다.
 A = ad - bc [ x2=a, y2=b, x3=c, y3=d 라고 두면 일치합니다. ]
 -> ad = A + bc [ bc를 이항 ]
 위의 식에서 d = M으로 가정합시다. 그러면 aM = A + bc가 되지요. 만약 A를 M으로 나눈 나머지가 k라면, bc를 M으로 나눈 나머지가 M - k일 때 위의 식은 a,b,c,d가 모두 정수가 될 수 있습니다. bc의 곱은 0 ~ M-1 이하의 숫자라고 볼 수 있으므로, c=1로 두면 b가 0 ~ M-1의 숫자임을 알 수 있습니다. b, c, d가 정해져있으면 a를 구하는것은 쉽고요.
  저는 대회 당시에는 위의 풀이까지는 접근하지 못하였고, c = 1로 둘 수 있다는 사실을 가지고 풀었습니다. c = 1이라는 사실만 알더라도 a의 값은 0 ~ N이기때문에 쉽게 접근할 수 있거든요 :)[/spoiler]
[spoiler="소스코드 보러가기..."]~~~ cpp

#include <cstdio>
#include <iostream>
using namespace std;
int N, M, A;
bool go() {
    if (N * M < A) return false;
    int a, b, c, d;
    c = 1, d = M; // Let c = 1, d = M 

    a = (A + (M - 1)) / M;
    b = (a * d - A);
    printf("0 0 %d %d %d %d\n", a, b, c, d);
    return true;
}
int main() {
    int T;
    cin >> T;
    for (int cn = 1; cn <= T; ++cn) {
        cin >> N >> M >> A;
        printf("Case #%d: ", cn);
        if (!go()) printf("IMPOSSIBLE\n");
    }
}

[/spoiler]

C. Star Wars

[문제 설명]

우주에 N대의 전함이 배치되어 있다. 각 전함의 좌표는 (xi, yi, zi)라고 하자. 각각의 전함은 파워 pi인 메시지 수신기를 가지고 있다. 모함에서는 각 전함들을 제어해야 하기 때문에 메시지를 보내야 하지만, 재정상의 문제로 출력이 아주 좋은 송신기를 구입하지는 못하였다.
모함이 (x, y, z)에 있고, i번째 전함이 (xi, yi, zi)에 위치해 있다고 가정하자. i번째 전함의 수신기의 파워가 pi라고 하면, 모함의 송신 능력은 최소한 ( | x - xi | + | y - yi | + | z - zi | ) / pi 이상이어야 한다는 것으로 알려졌다. 당신은 모든 전함에 메시지를 송신하기 위해 송신기를 한 대 구입하려고 한다. 하지만 위에서 설명했듯이 재정상의 문제로 최소 출력의 송신기를 구입하고자 한다. 모함은 적절히 배치할 수 있다고 가정할 때, 구입해야 할 송신기의 최소 출력을 구하시오.
[spoiler="풀이 보러가기..."]
[문제 풀이] -- 반례가 있는 풀이입니다.
이 문제의 핵심포인트는 문제를 얼마나 잘 이해하느냐 입니다. 많은 참가자분들이 문제를 잘못 이해하고 모든 구(sphere)의 교집합이 존재하는가? 를 풀려고 노력하다가 포기했다는 말을 하셨거든요.
3차원의 경우는 제가 그림을 그리기가 어려우므로 [...] 2차원으로 바꿔서 설명하겠습니다. 어차피 2차원일때를 이해한다면 3차원인 경우도 어렵지 않으니까요.
우선 (0, 0)을 기준으로 파워 K로 커버할 수 있는 범위를 x, y축을 기준으로 그림으로 나타내면 아래의 (그림 1)과 같이 다이아몬드 형태로 나온다는 사실을 알 수 있습니다. 3차원의 경우에는 정8면체가 나오게 되지요. 정8면체를 나타내는 방법이 생각만큼 간단하기 때문에 이 문제가 어렵게 느껴지는 것이겠지요. 하지만 x, y축을 약간 변형하여 x+y, x-y축으로 나타낸다면 아래의 (그림 2)와 같이 표현할 수 있습니다. 아래의 그림을 살펴보도록 합시다.

즉, 그림 1의 경우에는 | x | + | y | <= p 라는 식이었지만, 그림 2의 경우는 -p <= x+y <= p, -p <= x-y <= p 의 꼴이 된 셈이지요. 하나의 식을 둘로 나눴다고 생각할 수 있겠지만, 절대값 기호를 제거한 것 만으로도 충분히 의미가 있습니다. 또한 (그림 1)과 (그림 2)는 단순히 축을 변경한 것 뿐이기 때문에 (그림 1)에서 겹친다면 (그림 2)에서 겹치는 것은 자명합니다. 우리가 구하고자 하는 것은 (그림 1)에서 구한 범위들을 교집합 연산을 했을 경우에 그 구간이 존재하는 최소의 K입니다. 즉 "모든 범위의 교집합"을 구해야 하는 셈이지요. (그림 1)에서 교집합 연산을 한다면, 직사각형 모양이 나오게 되는데, 그렇게 되면 범위를 표현하기가 상당히 난감해집니다. 반면 (그림 2)에서 직사각형 모양을 표현한다면 두 개의 부등식으로 표현을 하면 되니 훨씬 용이하지요. (그림 2)에서 교집합을 구하는 것은 단순히 모든 부등식을 만족하는 값이 존재하느냐? 가 되니까요.
그러면 이제 K를 구해야 합니다. 이러한 K는 Binary Search를 이용하여 구하는데요. [L, R]의 범위 안에 답이 있다고 가정할 때, K = (L + R) / 2로 정하고 현재 K일때 답이 있느냐 없느냐를 구해봅니다. 만약 K일때 답이 존재한다면 [L, K]에 답이 있는 셈이고, 존재하지 않는다면 [K, R]에 답이 있다는 것을 알 수 있지요. 이러한 과정을 [L, R]의 구간의 크기가 매우 작아질때까지 반복하면 됩니다 :)
이제 원래의 문제인 3차원으로 돌아갑시다. 3차원의 경우는 x, y, z 이렇게 세 개의 축이 있는 공간도형이 됩니다. 이것을 (그림 2)에서처럼 변형하면 x+y+z, x+y-z, x-y+z, x-y-z 이렇게 4개의 수식이 나오게 됩니다. ( 4차원을 그림으로 표현하기는 너무너무 어렵네요 ㅇ<-< ) 이를 위에서 한 것처럼 교집합을 반복적으로 구하면 되지요. 소스코드를 참조하세요 [!]
[/spoiler]
[spoiler="소스코드 보러가기"] ~~~ cpp

#include
#include
#include
using namespace std;
int T, N;
typedef vector VI; // vector 가 길어서 VI로 재정의...
/* 처음엔 (-INF, INF) 구간을 설정하고 있다가 점점 좁혀나갑니다.

• 만약 교집합이 없다면 m일 때 불가능. 교집합이 있다면 m일 때 가능한 셈이지요. */ bool cango(VI x, VI y, VI z, VI p, double m) { pair range[4]; // x+y+z, x+y-z, x-y+z, x-y-z for (int i = 0; i < 4; ++i) { range[i].first = -1e10; range[i].second = 1e10; } for (int i = 0; i < x.size(); ++i) {// a >?= b 는 a = max(a, b)를 a <?= b 는 a = min(a, b)를 의미합니다. range[0].first >?= (x[i] + y[i] + z[i]) - p[i] * m; range[0].second <?= (x[i] + y[i] + z[i]) + p[i] * m; range[1].first >?= (x[i] + y[i] - z[i]) - p[i] * m; range[1].second <?= (x[i] + y[i] - z[i]) + p[i] * m; range[2].first >?= (x[i] - y[i] + z[i]) - p[i] * m; range[2].second <?= (x[i] - y[i] + z[i]) + p[i] * m; range[3].first >?= (x[i] - y[i] - z[i]) - p[i] * m; range[3].second <?= (x[i] - y[i] - z[i]) + p[i] * m; } for (int i = 0; i < 4; ++i) { if (range[i].first > range[i].second) return false; } return true; } int main() { cin >> T; for (int cn = 1; cn <= T; ++cn) { cin >> N; vector x(N), y(N), z(N), p(N); for (int i = 0; i < N; ++i) { cin >> x[i] >> y[i] >> z[i] >> p[i]; } double l = 0.0, r = 3.0 * 1e6, m; while (r - l >= 1e-9) { // binary search m = (l + r) / 2.0; if (cango(x, y, z, p, m)) { r = m; } else { l = m; } } printf("Case #%d: %lf\n", cn, r); } }

[/spoiler]
[spoiler="lazyboy님의 풀이..."] [lazyboy님의 풀이]-- (역시) 반례가 있는 풀이입니다.
  위의 알고리즘보다 쉽게 접근할 수 있는 방법입니다. Local Search 이지요. 임의의 점 (0, 0, 0)에서부터 시작하여 답이 점점 좋아하는 방향으로 진행합니다. 처음에는 많이 이동했다가 점점 조금씩 이동해서 어느정도 이상의 정확도를 보장하면 끝내는 알고리즘이지요. 어떻게 보면 이게 더 직관적이고 간단한 풀이일수도 있겠군요.
 ~~~ cpp

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<deque>
#include<map>
#include<functional>
#include<algorithm>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOREACH(i,x) for(typeof(x)::iterator it=(x).begin(); it!=(x).end(); ++it)
#define EACH(i,x) REP(i,(x).size())
#define sz    size()
#define all(x) (x).begin(), (x).end()
#define sqr(x) ((x)*(x))
#define pb    push_back
#define mp    make_pair
#define eps    1e-10
#define inf 0x3FFFFFFF
typedef long long int int64_t;
typedef long long int lint;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
vi x;
vi y;    
vi z;
vi p;
double cal(double xx, double yy, double zz)
{
    double ret = 0.0;
    EACH(i,x)
        ret = max(ret, (fabs(x[i]-xx)+fabs(y[i]-yy)+fabs(z[i]-zz))/p[i]);
    return ret;
}
void solve()
{
    int n;
    double ret = 0;
    x.clear();
    y.clear();
    z.clear();
    p.clear();
    scanf("%d",&n);
    REP(i,n) {
        int xx, yy, zz, pp;
        scanf("%d%d%d%d", &xx, &yy, &zz, &pp);
        x.pb(xx);
        y.pb(yy);
        z.pb(zz);
        p.pb(pp);
    }
    double xx = 0;
    double yy = 0;
    double zz = 0;
    double val = 1e+15;
    double delta = 1e+6;
    while(delta > eps) {
        double temp = val;
        double t;
        t = cal(xx+delta, yy, zz);
        if (t<temp) {
            xx += delta;
            temp = t;
        }
        t = cal(xx, yy+delta, zz);
        if (t<temp) {
            yy += delta;
            temp = t;
        }
        t = cal(xx, yy, zz+delta);
        if (t<temp) {
            zz += delta;
            temp = t;
        } 
        t = cal(xx-delta, yy, zz);
        if (t<temp) {
            xx -= delta;
            temp = t;
        }
        t = cal(xx, yy-delta, zz);
        if (t<temp) {
            yy -= delta;
            temp = t;
        }
        t = cal(xx, yy, zz-delta);
        if (t<temp) {
            zz -= delta;
            temp = t;
        }
        if (temp >= val - eps)
            delta *= .5;
        val = temp;
    }
    printf("%.6lf\n", val);
}
int main(void)
{
    int t;
    scanf("%d",&t);
    REP(i,t) {
        printf("Case #%d: ", i+1);
        solve();
    }
}

[/spoiler]

D. PermRLE
[문제 설명]
당신은 Run-Length Encoding을 조금 더 개량하여 PermRLE라는 이름의 알고리즘을 만들었다.
PermRLE란 어떤 문자열 S가 있을 때, 임의의 자연수 K와 1 ~ K로 이루어진 순열을 생성하고, 문자열을 K개씩의 구간으로 쪼개서 임의로 배열한 다음 이를 압축하는 알고리즘이다. 예를 들어 S = "abcdefghijkl"이고 K = 4, {3, 1, 4, 2} 라는 순열이 있으면 우선 이 문자열을 4개씩으로 묶어서 쪼개면 "abcd / efgh / ijkl"가 된다. 이를 {3,1,4,2} 순서로 배열한다. 즉 세번째 위치에 있는 c가 제일 처음에 첫번째 위치의 a가 가 그 뒤에, 마찬가지로 네번째 위치와 두번째 위치의 d, b가 순서대로 배열되는 것이다. 쪼갠 조각들에 대하여 같은 과정을 반복하면 "cadb / gehf / kilj" 가 되는 것이다.
이렇게 재배치한 문자열이 있을 때, PermRLE에서는 같은 문자열을 하나로 묶어서 표현한다. "aaabcaa" 라는 문자열이 있으면 "aaa", "b", "c", "aa"로 묶어서, 길이 4짜리 문자열이 된다.
어떤 String S와 K가 주어지면, 생성된 순열에 따라 PermRLE로 압축한 결과가 다르다는 것을 깨달았다. 순열을 임의로 생성할 수 있다고 할 때, PermRLE로 만들 수 있는 압축된 문자열의 최소 길이를 구하는 프로그램을 작성하시오.
[spoiler="풀이 보러가기..."] [문제 풀이]
Small Dataset은 K <= 5이기 때문에 쉽게 풀 수 있습니다. 모든 경우를 다 구한다고 해도 120 가지의 경우밖에 없기 때문이지요 ! 하지만 Large Dataset은 K가 최대 16이 될 수 있습니다. 20조가 넘는 경우의 수가 존재하지요. 이는 아무리 빠른 컴퓨터라도 8분 내에 구하기 힘듭니다 :)
Large Dataset의 경우는 문제를 살짝 변형해서 풀어야 합니다. 결론부터 말씀드리자면 이 문제를 도시가 최대 16개 있는 TSP(Traveling Salesman Problem)문제로 바꿀 수가 있지요.
TSP문제란 N개의 도시와 각 도시간의 거리가 입력으로 주어졌을 때, 모든 도시를 방문하고 시작점으로 돌아오는 이동경로의 거리를 최소화 하는 문제입니다. 이 문제도 모든 경로를 일일이 탐색한다면 O(N!)의 시간복잡도를 가지지만, O(N^2 * 2^N)의 알고리즘이 존재하지요. 이 알고리즘은 tsp dynamic으로 검색하면 자료가 많이 나올테니 검색을 활용해주세요 :) 힌트를 드리자면 table[i][j] = 현재 위치를 i로 두고, j에는 아직 방문하지 않은 점을 bit로 표현할 때의 최단 경로로 두면 됩니다.
이제 필요한 것은 문제의 변형이 되겠군요. TSP의 도시의 개념은 D번 문제에서 "string S를 (K로 나눈 나머지의 집합)" 으로 변형할 수 있습니다. "abcdefghijkl", K = 4일때 "aei", "bfj", "cgk", "dhl"의 4개의 도시라고 볼 수 있지요. 각각 0번도시, 1번도시, 2번도시, 3번도시라고 정의합시다. TSP의 0->2->1->3->0의 경로가 있다고 하면, D번 문제에서의 순열을 {1,3,2,4}라고 생각할 수 있고, 이 순열로 변환한 string은 acbd egfh ikjl라고 볼 수 있지요. 그러면 TSP에서의 입력으로 주어지는 '각 도시간의 거리'는 두 개의 string간의 다른 문자의 수 라고 두면 됩니다. 'abaa'와 'aabc'간의 거리는 3이 되는 식이지요. a-a, b-a, a-b, a-c에서 세 쌍의 다른 pair가 있으니까요. 다만 주의해야 할 점은 사이클을 이루는 (위의 0->2->1->3->0의 예에서는 3->0) 마지막 path는 거리가 다릅니다. 3의 i번째 character는 0의 i+1번째 character와 매치되기 때문이지요.
위의 설명과 함께 아래의 소스를 참조하시면 도움이 되리라 생각합니다 :) 이해가 되지 않는 부분이 있으시다면 hanirc의 #icpc채널을 찾아주세요! [/spoiler]
[spoiler="소스코드 보러가기(Small)"]~~~ cpp

#include
#include
#include
#include
#include
using namespace std;
int K, T;
string S;
vector perm;
int RLE(string S) {
char bef = S[0];
int ret = 1;
for (int i = 1; i < S.size(); ++i) {
if (bef != S[i]) {
bef = S[i];
ret++;
}
}
return ret;
}
int main() {
cin >> T;
for (int cn = 1; cn <= T; ++cn) {
cin >> K;
cin >> S;
perm.resize(K);
for (int i = 0; i < K; ++i)
perm[i] = i;
int ret = S.size();
do {
string S2 = "";
for (int i = 0; i < S.size(); i += K) {
for (int j = 0; j < K; ++j) {
S2 += S[i + perm[j]];
}
}
ret <?= RLE(S2); // S2의 RLE값을 구하여 최소값으로 갱신합니다.
} while (next_permutation(perm.begin(), perm.end())); // 다음 순열을 구하는 함수
printf("Case #%d: %d\n", cn, ret);
}
}

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
[spoiler="소스코드 보러가기(Large)"]~~~ cpp

#include <vector>
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int K, N;
int T;
string S;
int c[20][20]; // 각 vertex간의 거리를 저장
int d[20][20]; // 엇갈려서 매치한 거리.
int table[18][(1 << 16) + 2];
int st;
/* TSP dynamic version. 
 sv : start vertex
 set : unvisited -> 1, visited -> 0으로 이루어진 N자리 이진수. */
int memoi(int sv, int set) {
    if (set == 0) return table[sv][set] = d[st][sv];
    if (table[sv][set] != -1) return table[sv][set];
    int min = 9999999; /* set minimum = INF */
    for (int i = 0; i < N; ++i) {
        if (((set & (1 << i)) != 0) && (sv != i)) { /* 아직 가본 노드가 아니라면, 방문해 본다. */
            int tmp = memoi(i, set - (1 << i)); /* sv->i로 갔을때의 최단거리를 구한다. */
            min <?= c[sv][i] + tmp; /* 갱신 */
        }
    }
    return (table[sv][set] = min);
}
int main() {
    cin >> T;
    for (int cn = 1; cn <= T; ++cn) {
        cin >> K; N = K;
        cin >> S;
        memset(c, 0, sizeof(c));
        memset(d, 0, sizeof(d));
        /* 그래프를 만든다. */
        for (int i = 0; i < K; ++i) {
            for (int j = 0; j < K; ++j) {
                if (i == j) continue;
                for (int k = 0; k < S.size(); k += K) {
                    if (S[k + i] != S[k + j]) c[i][j]++;
                    if (k + K < S.size() && S[k + j] != S[k + K + i]) d[i][j]++;
                }
            }
        }
        int ret = 999999;
        for (int i = 0; i < K; ++i) {
            memset(table, -1, sizeof(table));
            st = i;
            ret <?= memoi(i, (1 << K) - 1 - (1 << i));
        }
        printf("Case #%d: %d\n", cn, ret + 1); // 마지막에 1을 더하는 이유는 제일 앞의 문자가 1개의 그룹을 만들기 때문입니다. "aaaaaa"를 생각하면 편할듯.
    }
}

[/spoiler]