[백준] 2169 로봇조종하기

1. 문제

www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

2. 접근방법

1,1 에서 N,M까지 가면서 최대 합을 가질 수 있는 경로를 찾는 문제

 

N이 1000까지 가능하니 bfs나 dfs를 이용해 완탐을 하면 터진다.

 

처음에는 pq를 사용해 보려 했으나 pq도 결국 완탐이 될 수 있어 터질 것 같아 도전하지 않았다.

 

결국 dp로 풀었는데

 

진행 가능 방향이 왼쪽 오른쪽 아래 뿐이라 위로 가는 경우가 없으니

한 줄씩 처리 해가야겠다 생각하였고

 

맨 첫줄은 1,1에서 시작이라 진행방향이 ->> 뿐이 안되니 각 자리에서 최댓값은 >>로 가는 값뿐이다.

 

이 예제에서는 dp 배열 첫줄은

10 35 42 50 63 이 될 것이다.

 

두번 째 줄 부터 중요한데

 

각 자리에 오는 방법은

1. 바로 위에서 내려오기

2. 왼쪽에서 오기

3. 오른쪽에서 오기

 

3가지다

 

왼쪽과 오른쪽은 어디서 꺽어서 오냐에 따라 값이 달라져

여러 경우가 있지 않나? 생각할 수 있지만

 

dp를 활용해 최대값을 구하며 오면 모든 경우를 볼 필요가 없다.

 

왼쪽과 오른쪽을 나눠서 생각해서

 

왼쪽 부터 보면

 

dp : [10 35 42 50 63]

68은 왼쪽에서 오는게 없으니 위쪽에서 오는 10을 받아

78이 가장 큰 값이 될 것이다.

 

다음 24 는 왼쪽 값 78과 위 값 25 중 더 큰 값에서 더하면 된다.

 

여기선 왼쪽 78과 24 를 더한 102가 된다.

 

다음 -78도 왼쪽 102와 위 7 중 큰 값과 더한 값이 된다.

 

이런 식으로 끝까지 값을 매기고

 

똑같은 방식으로 오른쪽에서 부터 시작해서

값을 구한 뒤

 

왼쪽에서 구한 값과 오른쪽에서 구한 값 중

더 큰 값을 dp에 저장 시키고

다음 줄로 이동 하면 된다.

 

끝까지 이동한 후 dp의 N,M 값만 출력 하면 된다.

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G1_2169로봇조종하기 {
	
	
	public static void main(String[] args) throws Exception {
		int N,M,map[][];
		int dp[][];
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		dp = new int [N][M];
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < M ; j++) 
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		dp[0][0] = map[0][0];
		for(int i = 1 ; i < M ; i++)
			dp[0][i] = dp[0][i-1]+ map[0][i]; 
		for(int i = 1 ; i < N ; i++) {
			int temp1 [] = new int [M];
			int temp2 [] = new int [M];
			temp1[0] = dp[i-1][0] + map[i][0];
			for(int j = 1 ; j < M ; j++) 
				temp1[j] =map[i][j]+ Math.max(temp1[j-1], dp[i-1][j]);
			
			temp2[M-1] = dp[i-1][M-1] + map[i][M-1];
			for(int j = M-2 ; j >= 0 ; j--)
				temp2[j] = map[i][j] + Math.max(temp2[j+1] , dp[i-1][j]);
			for(int j = 0 ; j < M ; j++) 
				dp[i][j] = Math.max(temp1[j], temp2[j]);
		}
		System.out.println(dp[N-1][M-1]);
		
	}

}

4. 마치며

꽤나 재밌는 문제였다.