[25568] 피라미드

문제 링크 : https://www.acmicpc.net/problem/25568

25568 - 피라미드

본문

 $3$가지 색상의 블록으로 이루어진 블록 피라미드가 있다. 피라미드는 $N$행으로 이루어져 있고, $i$ ($1\leq i \leq N)$행은 $i$개의 블록으로 이루어져 있다.

또한, $i$행의 $j$번째 블록을 $(i, j)$로 표현했을 때, $(i, j)$는 아래와 같은 조건에 의해 최대 $6$개의 다른 블록과 맞닿아 있다.

• $i \ge 2$ 이고 $j \ge 2$ 라면, $(i - 1, j - 1)$와 맞닿아 있다.
• $i \ge 2$ 이고 $j \le i - 1$ 라면, $(i - 1, j)$와 맞닿아 있다.
• $j \ge 2$ 라면, $(i, j - 1)$와 맞닿아 있다.
• $j \le i - 1$ 라면, $(i, j + 1)$와 맞닿아 있다.
• $i \le N - 1$ 라면, $(i + 1, j)$, $(i + 1, j + 1)$와 맞닿아 있다.

당신은 아름다운 블록 피라미드를 만들기 위해, 피라미드의 맞닿아 있는 블록의 색상이 같은 경우가 없도록 블록들을 재배치하고 싶다. 당신이 할 수 있는 연산은 아래 한 가지 뿐이다.

• $i\ (2 \le i \le N)$행의 블록 2$2$개를 골라 교환한다.

이 때, 목표를 이루기 위한 연산 사용 횟수의 최솟값을 출력하라.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 1\,000)$ 

두 번째 줄부터 $N$개의 줄에 걸쳐 블록 피라미드의 각 행의 상태가 주어진다. $i + 1$번째 줄에는 블록 피라미드의 $i$행을 이루는 블록 $i$개의 색상 정보가 공백을 사이에 두고 주어진다. 색상 정보는 $0$, $1$ 또는 $2$의 정수이며, 각각 $3$가지의 다른 색상을 표현한다.

출력

피라미드의 맞닿아 있는 블록의 색깔이 같은 경우가 없도록 하기 위한 연산 사용 횟수의 최솟값을 출력하라. 해당 연산만으로 목표를 이루는 것이 불가능하다면 -1을 출력하라.

제한

시간 제한	메모리 제한
1sec	1024MB

---

풀이

처음에는 피라미드 모양에 맞춰, 각 행에서의 교환을 최소화하는 dp문제로 이해하고 문제를 해결하려했다. 그러려면 피라미드 모양이 어떤 모양이 가능한지 정답을 그려보아야했다. 그래서 피라미드 모양이 가능한 경우의 개수를 찾아보았다.

• 1번째 줄은 교환할 블럭이 없다. 그 위치 고정
• 2번째 줄은 서로 교환할 수 있다. 1번째 줄의 블럭과 겹친다면 아예 불가능한 피라미드 모양
• 문제는 3번째 줄 이후부터이다
  • 3번째 줄을 예시로 생각하면, (3,2) 위치의 블럭은 색깔이 고정되어야한다. 이 블럭은 (2,1), (2,2) 블럭과 맞닿아있기 때문
  • 그렇다면, (3,1) 블럭은 (2,1)이랑 (3,2) 블럭과 맞닿아있기 때문에, 색깔이 고정된다
  • (3,3) 블럭 또한 (2,2), (3,2) 블럭과 맞닿아있기 때문에, 색깔이 고정된다
  • 즉, 2번째 줄 이후 3번째 줄부터는 모든 블럭이 고정되어야한다

그래서, 피라미드의 모양이 가능한 경우는 2번째 줄에 따라 2가지 경우밖에 존재하지 않는다는 결론에 도달할 수 있다. 2개밖에 없기 때문에 모든 경우에 대해 값을 찾아가도 될 것 같다. 피라미드의 모양은 2번째 줄에 의해서만 경우가 갈린다고 이해하고 풀어보자.

블럭이 1개밖에 없다면 그 자체로 피라미드의 모양을 만들 수 있으므로 0을 출력해야한다. 블럭이 2줄이라면 불가능한 피라미드인지만 확인하면 된다. 같은 색이 있다면 -1, 없다면 0일 것이다.

그 이후부터는 계산을 좀 해야한다. 3번째 줄부터는 2번째 줄의 형태에 따라 정답 피라미드가 이미 정해진다. 즉 특정 위치에서의 “현재 블럭이랑 정답 블럭”이 모두 주어질 수 있다. 우리는 현재 블럭과 정답 블럭이 다르다면, 블럭을 교환하여 정답 블럭으로 바꾸는 연산을 진행해야한다. 그 줄의 모든 위치에 대해 교환 행렬을 만들어서 기록해두자. 교환행렬 matrix[i][j]는 아래 의미를 가진다.

matrix[i][j] : i 색깔 블럭이 j 색깔 블럭으로 바뀌어야하는 경우의 개수

이 행렬을 만드는 이유는 문제의 형태를 축소시키기 위함이다. 최대 1000개의 블럭 배열을 모두 확인하며 계산하기보다는 9칸의 행렬만 계산하는 형태로 바꾸기 위함이다. 특히 case별로 압축하였기 때문에 특정 상황을 한번에 고려하여 계산할 수 있다.

그러면 행렬에 대해서 연산 횟수를 계산해보자. 일단 현재 있는 블럭 개수는 정답 피라미드에서 사용해야하는 블럭의 개수와 같아야한다. 아니라면 정답 피라미드를 만들 수 없으니 불가능 판정을 내리면 된다. 판정이 됐다면 블럭 교환 횟수를 계산할 수 있는데, 교환하는 방식이 여러 가지가 존재한다. 어떻게 하면 교환 횟수를 최소화할 수 있을까?

간단히 생각해보면 “서로 교환해야하는 블럭은 교환하는 것이 이득”이라는 점이 있다. case로 생각해보면 matrix[1][0]이랑 matrix[0][1]은 서로 교환해야하는 블럭이므로 서로 교환하는 것이 이득일 것이다. 왜냐면, matrix[1][0]의 경우, 1 -> 0으로 교환하면 교환횟수가 1번 사용되지만, 1 -> 2 -> 0으로 교환하면 교환횟수를 2번 사용하기 때문이다. 교환 횟수를 최소화해야하므로, 서로 교환되는 블럭은 교환하는 것이 이득이다.

그럼 교환 횟수는 어떻게 계산할 수 있을까? 단계별로 생각해보자.

• 어짜피 정답이 0인 위치에는 0 블럭을 두어야한다. 정답이 0인 위치에 먼저 0을 두도록 교환하자. 즉 matrix[1][0]과 matrix[2][0]들은 교환을 해야한다. 저 횟수만큼 교환을 하면서, 0 -> 1인 경우와 0 -> 2인 경우에 우선적으로 있는 0블럭들을 적절히 교환한다고 생각하자. 이것을 이득교환이라고 하자. 그러면 남은 것은 1 -> 2 교환과 2 -> 1 교환밖에 없다
• 남은 1 -> 2 교환과 2 -> 1 교환을 진행한다. 근데 이 교환 횟수를 구해야한다.
  • 0 블럭을 원위치시킬 때, 서로 이득교환인 경우를 제외하고 남는 블럭들이 있을 것이다. 만약 이득교환 이후에 0 블럭이 있어야할 위치에 1 블럭이 남아있는 경우, 2 블럭 위치에는 여분의 0 블럭이 있을 것이다
    • 이때까지의 교환 횟수는 min(matrix[1][0], matrix[0][1]) + min(matrix[2][0], matrix[0][2])이다. 다만 예시 상황에서 matrix[1][0] < matrix[0][1], matrix[2][0] > matrix[0][2]이므로 총 횟수는 matrix[1][0] + matrix[0][2]이다
  • 0 블럭 위치에는 모두 0 블럭만 놓아야한다. 다만 1 -> 0 인 상황에서 이득교환이 불가능하므로 “이득교환 이후” 남은 2 -> 0을 진행한다. 진행한 만큼 진행해야하는 matrix[2][1] 횟수가 증가한다
    • 이때까지의 추가 교환 횟수는 남아있던 matrix[2][0]이다. 이것은 이전의 matrix[0][2]와 합치면 원래의 matrix[2][0]이 되므로, 지금까지의 연산 횟수는 matrix[1][0] + matrix[2][0]이다
  • 이제 1 -> 2와 2 -> 1 교환을 진행한다. 이 때 정상적인 피라미드라면 이때까지의 matrix[1][2]와 matrix[2][1]의 개수가 같아야하고, 그만큼 교환을 진행해야한다
    • 이때 교환 횟수는 당연히 matrix[1][2]이다. matrix[2][1]에는 위 단계에서 case가 추가되어 계산되었으므로, 원래 matrix 값으로 비교하려면 matrix[1][2]만큼의 교환을 진행한다고 생각해야한다
  • 최종적으로 총 교환 횟수는 matrix[1][0] + matrix[2][0] + matrix[1][2]로 계산할 수 있다
    • 반대의 경우는 matrix[2][0] + matrix[1][0] + matrix[2][1]이다. 1번 단계에서, 어떤 블럭이 남느냐에 따라 matrix[1][2]를 더하게 될지 matrix[2][1]을 더하게 될지 결정되어진다
    • 그런데, 결국 어떤 상황이든 matrix[1][2]와 matrix[2][1]의 값 중 “더 큰 값”을 더하게된다. 왜냐면 2번 단계에서, 남는 블럭의 교환 횟수가 증가하는 경우가 있는데, 그것을 포함한 경우의 수가 반대 상황의 경우의 수와 같고, 그만큼 교환을 진행할 것이기 때문이다
• 결론적으로, 어떤 상황에서든지 피라미드의 각 행마다 matrix[1][0] + matrix[2][0] + max(matrix[1][2], matrix[2][1])번의 교환을 하면 피라미드를 만들어낼 수 있다는 것이다

위 과정을 구현해내면 답을 얻어낼 수 있다. 나머지는 직접 해보자.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 10

#include <stdio.h>

#define MAX_IDX 1000
int input[MAX_IDX][MAX_IDX];
int ans[MAX_IDX][MAX_IDX];
int n;

const int UNABLE = 9999999;

#define min(a, b) (((a) > (b)) ? (b) : (a))
#define max(a, b) (((a) > (b)) ? (a) : (b))

int solve() {
    int ret = 0;

    for (int i = 2; i < n; ++i) {
        int matrix[3][3] = {0};

        // 정답 피라미드와 교환 행렬 생성
        for (int j = 1; j < i; ++j) {
            ans[i][j] = 3 - (ans[i - 1][j - 1] + ans[i - 1][j]);
            ++matrix[input[i][j]][ans[i][j]];
        }
        ans[i][0] = 3 - (ans[i - 1][0] + ans[i][1]), ans[i][i] = 3 - (ans[i - 1][i - 1] + ans[i][i - 1]);
        ++matrix[input[i][0]][ans[i][0]], ++matrix[input[i][i]][ans[i][i]];

        // 가능한 피라미드인지 체크
        if (matrix[0][1] + matrix[0][2] != matrix[1][0] + matrix[2][0]) {
            return UNABLE;
        }
        if (matrix[1][0] + matrix[1][2] != matrix[0][1] + matrix[2][1]) {
            return UNABLE;
        }
        if (matrix[2][0] + matrix[2][1] != matrix[0][2] + matrix[1][2]) {
            return UNABLE;
        }

        // 교환 횟수 계산
        ret += (matrix[1][0] + matrix[2][0] + max(matrix[1][2], matrix[2][1]));
    }

    return ret;
}

int main() {
    scanf("%d", &n);
    if (n == 1) {
        printf("0");
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            scanf("%d", &input[i][j]);
        }
    }

    if (input[0][0] == input[1][0] || input[1][0] == input[1][1] || input[1][1] == input[0][0]) {
        printf("-1");
        return 0;
    }

    ans[0][0] = input[0][0], ans[1][0] = input[1][0], ans[1][1] = input[1][1];
    int r1 = solve();

    ans[0][0] = input[0][0], ans[1][0] = input[1][1], ans[1][1] = input[1][0];
    int r2 = solve();

    if (r1 == UNABLE && r2 == UNABLE) {
        printf("-1");
    } else {
        printf("%d", min(r1, r2 + 1));
    }

    return 0;
}

• ans[][] : 현재 상황에 맞는 피라미드의 모양을 계산하여 기록
• input[][] : 입력으로 주어지는 피라미드
• matrix[][] : 위치를 바꿔야하는 그래프를 기록
  • matrix[a][b] : 현재 a 색깔의 블럭이 있는데, 그 위치의 정답은 b인 경우의 개수