[Java] 백준(Baekjoon) 11048. 이동하기

 

 

 

---

 

풀이

1) 주어진 사탕의 수 행렬이름이 grp라 하자

grp[3][4]

3 4
1 2 3 4
0 0 0 5
9 8 7 6

 

2) 해당 좌표까지의 최대치를 저장한 배열을 sum이라 하자

sum[3][4]

1 3 6 10

1 3 6 15

10 18 25 31

 

<규칙>

1-1. n이 1일때, sum[1][m]=sum[1][m-1]+grp[1][m]

1-2. m이 1일때, sum[n][1]=sum[n-1][1]+grp[n][1]

 

1-3. 다른 경우, sum[n][m] = max(sum[n-1][m], sum[n][m-1]) + grp[n][m]

 

=> 이를 코드로 표현하기

package dp;

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

public class Ex11048 {
	
	static int[][] grp;
	static int[][] sum;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int n= Integer.parseInt(st.nextToken());
		int m= Integer.parseInt(st.nextToken());
		
		grp = new int[n][m];
		sum = new int[n][m];
		
		for(int i=0;i<n;i++) {
			s = br.readLine();
			st = new StringTokenizer(s);
			
			for(int j=0;j<m;j++) {
				int num = Integer.parseInt(st.nextToken());
				grp[i][j]=num;
				
			}
		}

		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(i==0&&j==0) sum[i][j]=grp[i][j];
				else if(i==0) sum[i][j]=sum[i][j-1]+grp[i][j];
				else if(j==0) sum[i][j]=sum[i-1][j]+grp[i][j];
				else {
					sum[i][j] = Math.max(sum[i-1][j], sum[i][j-1]) + grp[i][j];
				}
				
			}
		}
		
		System.out.println(sum[n-1][m-1]);
		
	}

}