2169 로봇 조종하기 - 백준

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

2169번: 로봇 조종하기

풀이

로봇의 지형은 N*M

왼쪽, 오른쪽, 아래로만 이동 가능

한번 탐색한 지형은 탐사 불가

 

1,1 -> N, M 이동

 

첫째 줄

N, M

N개의 줄에 M개의 수 배열

 

최대 가치 출력

 

맵에서 현재 위치(i, j)   -> 이전 위치(i, j-1), (i, j+1), (i-1,j)

좌위에서 한번, 우위에서 한번 계산해서 둘 중 더 큰 수를 대입

첫째줄

dp	0	1	2	3	4
0	10	10+25 =35	10+25+7=42	10+25+7+8=50	10+25+7+8+13=63
1
2
3
4

 둘째 줄(i,0) (왼쪽, 위쪽 계산)

temp	0	1	2	3	4
0	dp[0][0] + arr[1][0] = 78	max(temp[0][1],dp[0][1]) + arr[1][1] = max(78, 35) + 24 = 102	max(temp[0][1],dp[0][2) + arr[1][2] = max(102,42) -78 = 24	max(temp[0][2],dp[0][3]) + arr[1][3]  = max(24, 50) + 63 = 113	max(temp[0][3],dp[0][4]) + arr[1][4] = max(113,63) + 32 = 145
1

 (오른쪽, 위쪽 계산)

temp	0	1	2	3	4
0	dp[0][0] + arr[1][0] = 78	max(temp[0][1],dp[0][1]) + arr[1][1] = max(78, 35) + 24 = 102	max(temp[0][1],dp[0][2) + arr[1][2] = max(102,42) -78 = 24	max(temp[0][2],dp[0][3]) + arr[1][3]  = max(24, 50) + 63 = 113	max(temp[0][3],dp[0][4]) + arr[1][4] = max(113,63) + 32 = 145
1	max(temp[1][1], d[0][0]) + arr[1][0] = max(104, 10) + 68 = 172	max(temp[1][2], d[0][1]) + arr[1][1] = max(80,35) + 24 = 104	max(temp[1][3], d[0][2]) + arr[1][2] = max(158,42 ) -78 = 80	max(temp[1][4], d[0][3]) + arr[1][3] = max(95, 50) + 63 = 158	dp[0][4] arr[1][4] = 95

 dp값은 temp 2개 비교해서 큰값을 넣는다.

dp	0	1	2	3	4
0	10	10+25 =35	10+25+7=42	10+25+7+8=50	10+25+7+8+13=63
1	172	104	80	158	145
2
3
4

 

 값을 채워 넣으면

dp	0	1	2	3	4
0	10	10+25 =35	10+25+7=42	10+25+7+8=50	10+25+7+8+13=63
1	172	104	80	158	145
2	184	160	229	186	161
3	168	150	172	227	260
4	272	265	341	352	319

 

 

점화식

1. 첫 줄은 왼쪽부터 채워 넣기

2. 두 번째 줄부터는 왼쪽에서 한번 오른쪽에서 한 번 계산해서 큰수를 채워 넣기

코드

package test2169;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int M;

	static int[][] arr;
	static int[][] dp;
	static int[][] temp;

	static int[] dx = { -1, 1, 0 };
	static int[] dy = { 0, 0, 1 };

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		arr = new int[N][M];
		dp = new int[N][M];
		temp = new int[2][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		dp[0][0] = arr[0][0];

		// 첫번째 줄
		for (int i = 1; i < M; i++) {
			dp[0][i] = dp[0][i - 1] + arr[0][i];
		}

		// 두번째 줄 ~
		for (int i = 1; i < N; i++) {

			// 왼 위
			temp[0][0] = dp[i - 1][0] + arr[i][0];
			for (int j = 1; j < M; j++) {
				temp[0][j] = Math.max(temp[0][j - 1], dp[i - 1][j]) + arr[i][j];
			}

			// 오 위
			temp[1][M - 1] = dp[i - 1][M - 1] + arr[i][M - 1];
			for (int j = M - 2; j >= 0; j--) {
				temp[1][j] = Math.max(temp[1][j + 1], dp[i - 1][j]) + arr[i][j];
			}

			// dp update
			for (int j = 0; j < M; j++) {
				dp[i][j] = Math.max(temp[0][j], temp[1][j]);
			}
		}

		sc.write(dp[N - 1][M - 1] + "\n");

		sc.close();

	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		String nextLine() throws IOException {
			return reader.readLine();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}