[BAEKJOON] 백준 3991: 한번 쏘면 멈출 수 없어 (C#)

문제 링크

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

 

 

문제

은기는 모바일 게임 개발자이다. 이번에 은기가 만드는 게임은 Chain Shot! 게임 (SameGame, Jawbreaker, Bubble Shot, ... 으로도 알려져 있다)을 응용한 "한번 쏘면 멈출 수 없어" 이다.

게임은 직사각형 게임판에서 진행되며, 각 칸에는 색칠된 구슬이 채워져 있다. 플레이어는 각 턴마다 같은 색으로 이루어진 인접한 구슬 그룹을 선택한다. 선택한 구슬은 모두 게임판에서 제거된다. 구슬이 떠있는 경우에는 모두 바닥으로 떨어지게 되고, 빈 열은 제거된다.

각 턴마다 플레이어가 얻는 점수는 그룹을 구성하는 구슬 개수의 제곱이다. 예를 들어, 위의 그림에서 플레이어는 49점을 받게 된다.

게임판에 구슬이 모두 없어지면 게임은 끝나게 되고, 플레이어의 점수는 각 턴마다 얻은 점수의 합이 된다.

레벨의 설계도는 게임판의 크기와 각 구슬 색상의 수로 이루어져 있다.

레벨의 설계도가 주어졌을 때, 설계도로 만들 수 있는 레벨 중 얻을 수 있는 점수가 가장 높은 것을 구하는 프로그램을 작성하시오. 

 

 

입력

입력으로 레벨의 설계도가 주어진다.

첫째 줄에는 게임판의 행의 수 h와 열의 수 w, 색상의 수 c가 주어진다. (1 ≤ h, w ≤ 10, 1 ≤ c ≤ 9)

둘째 줄에는 c개의 양의 정수가 주어지며, 각 정수는 그 색상 구슬의 개수이다. 구슬 개수의 합은 h·w가 된다.

 

출력

만든 게임판을 출력한다. 첫 번째 색상은 1, 두 번째 색상은 2, ... 로 출력한다.

 

 

 

통과한 답안

using System.Text;

namespace _3991
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int h = int.Parse(inputs[0]);
            int w = int.Parse(inputs[1]);
            int c = int.Parse(inputs[2]);
            int[] marbles = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            StringBuilder sb = new StringBuilder();

            int[,] board = new int[h, w];

            int color = 1;
            int idx = 0;

            for (int i = 0; i < h; i++)
            {
                if (i % 2 == 0)
                {
                    for (int j = 0; j < w; j++)
                    {
                        if (marbles[idx] > 0)
                        {
                            board[i, j] = color;
                            marbles[idx]--;
                        }
                        else
                        {
                            idx++;
                            color++;
                            board[i, j] = color;
                            marbles[idx]--;
                        }
                    }
                }
                else
                {
                    for (int j = w - 1; j >= 0; j--)
                    {
                        if (marbles[idx] > 0)
                        {
                            board[i, j] = color;
                            marbles[idx]--;
                        }
                        else
                        {
                            idx++;
                            color++;
                            board[i, j] = color;
                            marbles[idx]--;
                        }
                    }
                }
            }

            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    sb.Append(board[i, j]);
                }
                sb.AppendLine();
            }

            Console.WriteLine(sb.ToString());
        }
    }
}

 

게임판의 행과 열, 색상의 수, 각 색상의 구슬의 수가 주어진다.

각 칸에 색칠된 구슬로 채워진 게임판에 대해서

같은 색으로 인접한 구슬 그룹을 선택하고, 그 구슬들은 모두 제거되며

제거된 구슬의 개수의 제곱만큼 점수를 얻는다.

이러한 규칙을 가지는 게임을 만드는 경우, 점수를 가장 높게 얻는 게임판을 만드는 문제이다.

 

점수는 제거한 구슬의 개수의 제곱의 합이므로,

최대한 많은 구슬을 한 번에 제거하는 것이 가장 높은 점수를 얻는 방법이다.

즉, 여러 경우의 수를 계산할 필요 없이 주어진 조건에서

한 번에 가장 많은 구슬을 제거하는 방법을 찾으면 된다.

 

이는 한 번에 한 색상의 구슬을 모두 제거하는 방법을 이용하면 된다.

문제의 예제에서도 4개 4개 7개가 주어졌을 때,

2번 4개, 1번 4개, 3번 7개를 삭제하는 방식으로 최고 점수를 얻었는데,

실제로는 예제처럼 복잡하게 게임판을 생성하지 않아도 된다.

가장 간단하게 게임판을 생성하는 방법은 이동 없이 계속해서 지울 수 있게 만드는 것인데,

가장 위쪽의 색상부터 차례대로 지우면 게임판의 이동이 없으므로

이동에 따른 변수를 차단할 수 있다.

 

문제를 해결하는 방법으로 좌측상단(0, 0)부터 스네이크 방식으로 구슬을 채우는 것이다.

(0, 0)부터 (0, w)까지 채우고 그 다음줄은 (1, w)부터 (1, 0)까지 채우는 방식)

1234
8765
910..

이렇게 구슬을 채운다면 구슬 제거에 따른 이동이 없으며,

한 번에 제거로 같은 색상의 모든 구슬을 제거할 수 있게 된다.

 

이를 구현하기 위해서 이중 for문에서 if문을 이용해서 i가 짝수인지 홀수인지에 따라서

j의 이동 방향을 정방향과 역방향을 설정함으로써 구현하였다.

 

또, 출력에서의 시간 초과를 방지하기 위해 StringBuilder를 이용하여

한 번에 출력하도록 구현하였다.