이번 문제는 백준의 골드 5 문제 주사위 쌓기 문제이다.
문제를 차근차근 한 번 읽어보자.
최대 10000개의 주사위가 주어지며, 주사위의 모든 면이 주어진다.
기존의 주사위와는 다른 형태로 면이 무작위하게 주어진다.
또한, 반드시 윗 주사위의 윗면과 아래 주사위의 아랫면이 동일해야 한다.
즉 1번 주사위의 위 아래가 고정되면 모든 주사위도 정해지게 된다.
이 때 주사위 옆면의 합이 최대가 되도록 해달라고 한다.
사실 주사위 옆면은 크게 문제가 되지 않는다.
위 아래만 고정되면, 해당 상태에서 최대 값만 고르면 되기 때문이다.
문제는 위 아래를 고정시키는 6가지 경우를 구현하는 것이다.
10000개의 주사위와 6개의 면이므로, 시간초과는 걱정하지 않아도 될 것 같다.
위 아래 짝
주사위의 특징은 위 아래면 짝이 정해져 있다는 점이다.
따라서 배열에 위 아래면 번호를 저장하여 짝을 미리 저장할 수 있다.
void init_pair() {
top_pair[0] = 5;
top_pair[1] = 3;
top_pair[2] = 4;
top_pair[3] = 1;
top_pair[4] = 2;
top_pair[5] = 0;
}위와 같이 배열에 미리 짝 번호를 저장하고 이후에 가져다 쓰도록 하자.
경우의 수 구현
단순히 for문을 6번 돌며 최초의 윗면을 정하도록 하자.
for (int i = 0; i < 6; i++) {
sum = 0, max_v = 0;
for (int j = 1; j <= 6; j++)
if (j != dice[0][i] && j != dice[0][top_pair[i]])
max_v = max(max_v, j);
sum += max_v;
// 위, 아래면 제외 가장 큰 값 찾아서 더해주기
std_top = dice[0][i];윗 면을 가장 바깥 for문으로 정해주고, 첫 주사위의 최대 값을 찾는다.
i, top_pair[i]가 위 아래면의 번호가 되어줄 것이다.
따라서 두 면을 제외한 나머지 옆 면 중 최대 값을 찾는다.
std_top은 최초의 주사위 윗 면이 되며, 다음 주사위의 기준이 된다.
for (int j = 1; j < num; j++) {
max_v = 0;
for (int k = 0; k < 6; k++) {
// 현재 보고있는 주사위의 윗면
if (dice[j][k] == std_top) {
curr_bottom = k;
break;
}
}
int top = dice[j][top_pair[curr_bottom]];
int bottom = std_top;
// 윗면은 이전 주사위의 윗면의 반대편
// 아랫면은 이전 주사위의 윗면과 같다.
for (int k = 1; k <= 6; k++)
if (k != top && k != bottom)
max_v = max(max_v, k);
sum += max_v;
std_top = top; // 윗면을 옮겨줘야 함
}다음 주사위부터는 이전 주사위의 윗면을 따라간다.
bottom이 std_top과 동일한 면을 가져가며,
top은 dice[j][top_pair[curr_bottom]]이 된다.
이는 이전 주사위의 윗면이 현재 주사위의 아랫면과 같도록 구현한 것이다.
이제 동일하게 최대 값을 구해서 sum에 더해주면 된다!
구현 문제를 풀 때 생각한대로 구현하는 능력이 아직 부족하다.
구현 문제를 조금 더 연습해야 할 것 같다.