1. 문제

28017번: 게임을 클리어하자



2. 개요

M개 종류의 무기가 있는 게임을 N회 플레이하려고 한다.

이 게임은 플레이마다 능력치가 초기화되어 사용하는 무기의 효율이 매번 달라진다.

또한 더 재미있는 플레이를 위해 이전 회차에 사용한 무기는 사용하지 않기로 한다.

각 회차마다 각 무기에 대한 게임 클리어 시간이 주어졌을 때, N회 클리어까지 걸리는 최소 시간을 구하는 문제.



3. 풀이 및 코드

3-1. 풀이

N번째 플레이를 한다고 생각했을 때, 각 무기의 클리어까지의 시간 + 이전 회차까지의 클리어시간의 총합의 최솟값이 N번째 클리어 시의 최소시간이 된다.

즉, i회차 때의 각 무기를 이용했을 시, i회차까지의 클리어 시간을 저장할 dp테이블을 만든다.

만들어둔 dp테이블로 i회차의 각 무기의 시간 + 이전 회차의 최솟값을 더해나가면 된다.

그러나 이전 무기는 사용 불가능하다는 조건이 있어서+ 최소의 경우가 불가능한 경우가 있는데, 이 때는 이전 회차까지의 총 플레이시간 중 두 번째로 작은 값을 더해나가주면 된다.

dp테이블을 완성한 후 마지막 행의 최솟값을 출력한다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

infos = []
dp = [[0 for i in range(M)] for j in range(N + 1)]

for i in range(N):
    info = list(map(int, sys.stdin.readline().split()))
    infos.append(info)

    s_info = sorted(dp[i])
    m1, m2 = s_info[0], s_info[1]

    if i == 0:
        for j in range(M):
            dp[i][j] = infos[i][j]

    for j in range(M):
        if dp[i][j] == m1:
            dp[i+1][j] = infos[i][j] + m2

        else:
            dp[i+1][j] = infos[i][j] + m1

print(min(dp[-1]))

3-3. C#

namespace boj_28017
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]), M = int.Parse(input[1]);

            int[,] infos = new int[N, M];
            List<int[]> dp = new();

            for (int i = 0; i < N + 1; i++)
                dp.Add(new int[M]);

            for (int i = 0; i < N; i++)
            {
                input = sr.ReadLine().Split();

                for (int j = 0; j < M; j++)
                    infos[i, j] = int.Parse(input[j]);

                int[] s_info = dp[i].OrderBy(x => x).ToArray();
                int m1 = s_info[0], m2 = s_info[1];

                if (i == 0)
                {
                    for (int j = 0; j < M; j++)
                        dp[i][j] = infos[i, j];
                }

                for (int j = 0; j < M; j++)
                {
                    if (dp[i][j] == m1)
                        dp[i + 1][j] = infos[i, j] + m2;

                    else
                        dp[i + 1][j] = infos[i, j] + m1;
                }
            }

            sw.WriteLine(dp[^1].Min());
            sw.Close();
        }
    }
}

Comments