[백준] 28017 - 게임을 클리어하자
1. 문제
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