[ 백준 5475, IOI 2007 Day 2 ] 광부들의 식사(Miners)

문제 링크

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

https://oj.uz/problem/view/IOI07_miners

문제 요약

광부들은 자신이 최근에 먹은 세 끼의 종류에 따라 캐는 석탄의 양이 달라진다. 다 다를 경우 3, 두 종류 일 경우 2, 한 종류 일 경우 1이다.

들어오는 식사의 개수의 종류는 3개이고, 광산은 총 2개 있다. 식사가 들어가지 않으면 0개의 석탄이 생산된다. 광부들이 최대로 생산해낼 수 있는 석탄의 양을 구하여라.

dp 배열들의 정의와 그것을 통한 아이디어 끌어오기

cost[i][j][k]=음식의 순서가 차례대로 i,j,k로 들어왔을 때 얻을 수 있는 석탄의 양

비어 있는 경우는 3으로 정의한다.

비어 있는 경우는 맨 처음 생기게 된다. 아무것도 없는 상황에서 첫 번째 음식이 광산으로 들어오면 그때에는 3,3,1을 부르게 된다.

cost 배열 정의

1) i=3

i=3일 때에는 j의 값에 따라 값이 달라진다.

만약 j가 3이면, 이제 새로 들어오는 경우기 때문에 무조건 1이다.

j가 3이 아니면, j와 k가 같냐 다르냐에 따라 달라진다.

j와 k가 같으면 1이고, 다르면 2이다.

2) i!=3

i와 j와 k가 모두 같을 시에 1을, i와 j와 k가 모두 다를시엔 3을, 그 외의 경우엔 2를 담는다.

dp 배열 정의

dp[i][j][k][l][v] : 현재 i-1번쨰 식사 지급 차례가 끝났으며, 첫 번째 광산에는 j와 k가, 두 번쨰 광산에는 l과 v가 들어가 있는 상태

현재 주어지는 식사를 t라고 하면,

이렇게 되면, dp[i][j][k][l][v]가 0보다 크거나 같을 때 다음과 같은 점화식을 생각할 수 있다.

$\begin{aligned}dp[i+1][k][t][l][v] ={\max\limits_{j,k,l,v =0}^{3}}(dp[i+1][k][t][l][v],cost[j][k][t]+dp[i][j][k][l][v])\\dp[i+1][j][k][v][t] ={\max\limits_{j,k,l,v =0}^{3}}(dp[i+1][j][k][v][t],cost[l][v][t]+dp[i][j][k][l][v])\end{aligned}$

차례대로 계산해주고, 마지막엔 i,j,k,l을 차례대로 0에서 3까지 돌면서 최대 크기를 호출해내면 답이다.

코드

https://oj.uz/submission/56101