문제 링크
문제
티어: 골드 1
알고리즘: dp
실버런(Silver Run)은 2차원 맵에서 캐릭터를 조종해서 최대한 많은 실버를 모으는 것이 목적인 모바일 게임이다.
실버런의 맵에는 실버 주머니들이 상하좌우로 일정한 간격을 두고 N행 M열의 직사각형 모양으로 배치되어 있으며, 각 주머니에는 정해진 개수만큼의 실버가 들어 있다.
편의상 상하좌우로 이웃한 실버 주머니 사이의 간격을 한 칸이라고 표현하며, 가장 왼쪽 위 주머니로부터 왼쪽으로 한 칸, 위로 한 칸 떨어진 위치로부터 아래로 x칸, 오른쪽으로 y칸 떨어진 위치를 (x, y)라고 표현한다. 즉 가장 왼쪽 위 주머니의 위치는 (1, 1), 가장 오른쪽 아래 주머니의 위치는 (N, M)이다.
게임이 시작되면 실버 주머니들은 1초당 한 칸의 일정한 속도로 왼쪽으로 움직이며, 유저는 캐릭터를 이동시키며 캐릭터와 부딪히는 실버 주머니에 든 실버를 획득하게 된다.
캐릭터와 주머니의 크기는 충분히 작아서, 실버를 획득하기 위해서는 캐릭터와 주머니의 위치가 정확히 일치해야 한다.
이 게임에서 가장 좋은 캐릭터는 16silver라는 캐릭터이다. 16silver는 임의의 위치에서 출발할 수 있으며(정수 좌표가 아니어도 된다!), 1초당 한 칸의 일정한 속도로 위, 아래 또는 오른쪽으로 이동할 수 있다. 그러나 제자리에 멈춰 있을 수는 없으며, 1초 단위로만 이동 명령을 내릴 수 있다. 예를 들어 "위로 2.5초 동안 이동"과 같은 명령은 내릴 수 없다.
맵이 주어질 때, 16silver 캐릭터를 이용해 모을 수 있는 실버의 최대 수량을 구하는 프로그램을 작성해 보자.
입력
첫 번째 줄에 맵에 있는 실버 주머니들이 이루는 직사각형의 행과 열 수를 나타내는 정수 N, M(1 ≤ N, M ≤ 1,000)이 공백을 사이에 두고 주어진다.
다음 N개의 줄에 걸쳐 각 줄에 M개의 정수가 주어진다. i번째 줄의 j번째 정수는 (i, j) 위치에 있는 실버 주머니에 들어 있는 실버의 양이며, 입력되는 모든 정수는 0 이상 100,000 이하이다.
출력
첫 번째 줄에 16silver 캐릭터로 모을 수 있는 실버의 최대 수량을 출력한다.
풀이
16silver 캐릭터로 모을 수 있는 실버의 최대 수량을 출력해야 한다.
먼저, 캐릭터를 위치시킬 좌표를 일반화해야 한다.
캐릭터의 출발 좌표는 정수, 실수 둘 다 가능하다고 한다.
정수라면 어디에 위치시켜야 할까? (x는 열의 좌표, y는 행의 좌표)
x가 1 ~ 5일 때 보다 0일 때가 모든 라인에 실버를 얻을 수 있기 때문에 x는 0이어야 한다.
y는 각 라인의 실버와 같아야 한다. 왜냐하면 캐릭터와 주머니의 위치가 정확히 일치해야 하기 때문이다. 그래서
정수일 때 캐릭터의 출발 좌표는 (0, 1), (0, 2), (0, 3)..,(0, N)가 된다.
다음은 좌표가 실수일 때 어디에 위치시킬지다.
x좌표는 0과 첫 번째 실버 사이에 위치시킨다. (정수와 같은 이유) 그러면 대략 0.1 ~ 0.9 사이라고 가정한다.
y좌표는 어떻게 위치시켜야할까? 다음과 같이 세 가지로 나눌 수 있다.
- 정수인 y좌표 (주머니와 같은 y)
- 실수인 위쪽 y좌표
- 실수인 아래쪽 y좌표
여기서 첫 번째 정수인 y좌표는 정수 (x, y) 좌표와 똑같이 움직이는 것을 알 수 있다.
그래서 첫 번째를 제외하고, 두, 세 번째는 아에 다르게 움직이기 때문에 이러한 경우들도 따져봐야 한다.
각 경우의 움직임에 따라서 얻는 주머니나 위치는 그려보면 쉽게 알 수 있을 것이다.
위 풀이를 토대로 dp를 정의하면 총 3가지 상태가 존재하며, 각 상태마다 좌표가 필요하기 때문에
dp[S][M][N]이 된다.
그래서 dp[0][2][2]는 정수 상태이면서, 현재 2번 째 라인에 2번 째 행에 있을 때 최적 값을 의미한다.
전체 상태는 3 x 1000 x 1000이기 때문에 충분히 가능한 경우의 수이고, 나는 재귀 방식을 통해 답을 구했다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //행
M = Integer.parseInt(st.nextToken()); //열
int[][] map = new int[M + 1][N + 1]; //어떤 라인에 어떤 행에 어떤 값이 있는 지를 저장
for(int i=1; i<=N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int j=1; j<=M; j++) {
map[j][i] = Integer.parseInt(st2.nextToken());
}
}
long[][][] dp = new long[3][M + 1][N + 1]; //3가지 타입, 어떤 라인에 어떤 행에 있을 때 최적값
initDp(dp); //-1은 탐색하지 않은 영역.
long answer = 0;
for(int i=1; i<=N; i++) {
for(int j=0; j<3; j++) {
answer = Math.max(answer, findAnswer(j, 0, i, map, dp));
}
}
System.out.println(answer);
}
static long findAnswer(int s, int r, int c, int[][] map, long[][][] dp) {
if(r >= M) {
return 0;
}
//가능한 영역
if(dp[s][r][c] != -1) {
//이미 방문했다면.
return dp[s][r][c];
}
//방문하지 않았다면
int nextR = r;
int nextC = c;
long up = 0;
long down = 0;
long right = 0;
if(s == 0) {
//정수
//위
nextR = r + 1;
nextC = c - 1;
if(1 <= nextC && nextC <= N) {
up += map[nextR][nextC];
up += findAnswer(s, nextR, nextC, map, dp);
}
//아래
nextC = c + 1;
if(1 <= nextC && nextC <= N) {
down += map[nextR][nextC];
down += findAnswer(s, nextR, nextC, map, dp);
}
//오른쪽
nextR = r + 2;
nextC = c;
right += map[r + 1][nextC];
if(nextR <= M) {
right += map[nextR][nextC];
}
right += findAnswer(s, nextR, nextC, map, dp);
} else if(s == 1) {
//실수, 위
//위
nextR = r + 1;
nextC = c - 1;
if(1 <= nextC && nextC <= N) {
up += map[nextR][nextC];
up += findAnswer(s, nextR, nextC, map, dp);
}
//아래
nextC = c + 1;
if(1 <= nextC && nextC <= N) {
down += map[nextR][c];
down += findAnswer(s, nextR, nextC, map, dp);
}
} else {
//s == 2 영역
//실수, 아래
//위
nextR = r + 1;
nextC = c - 1;
if(1 <= nextC && nextC <= N) {
up += map[nextR][c];
up += findAnswer(s, nextR, nextC, map, dp);
}
//아래
nextC = c + 1;
if(1 <= nextC && nextC <= N) {
down += map[nextR][nextC];
down += findAnswer(s, nextR, nextC, map, dp);
}
}
long v = up;
v = Math.max(v, down);
v = Math.max(v, right);
dp[s][r][c] = v;
return dp[s][r][c];
}
static void initDp(long[][][] dp) {
for(int i=0; i<dp.length; i++) {
for(int j=0; j<dp[i].length; j++) {
for(int k=0; k<dp[i][j].length; k++) {
dp[i][j][k] = -1;
}
}
}
}
}