[Baekjoon] 9844_Gecko

문제(출처: https://www.acmicpc.net/problem/9844)

---

< Gecko >

 

문제 풀이 

 

아래 행으로 내려오면서 최댓값을 구한다. 

 

my solution (Java)

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

public class _9844_ { // Gecko

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());

		int arr[][] = new int[h][w];
		int dp[][] = new int[h][w];

		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < w; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (i == 0) {
					dp[i][j] = arr[i][j];
				}
			}
		}

		for (int i = 1; i < h; i++) {
			for (int j = 0; j < w; j++) {
				dp[i][j] = Math.max(dp[i][j], arr[i][j] + dp[i - 1][j]);

				if (j - 1 >= 0) {
					dp[i][j] = Math.max(dp[i][j], arr[i][j] + dp[i - 1][j - 1]);
				}
				if (j + 1 < w) {
					dp[i][j] = Math.max(dp[i][j], arr[i][j] + dp[i - 1][j + 1]);
				}
			}
		}

		int result = 0;
		for (int i = 0; i < w; i++) {
			result = Math.max(result, dp[h - 1][i]);
		}

		System.out.println(result);
	}
}

변수)
h, w : 벽의 크기
arr : 각 타일의 모기 개수
dp : 각 위치까지 먹을 수 있는 모기 최대 개수
result : 먹을 수 있는 모기의 최대 개수

 

벽의 크기를 입력받는다. 벽의 크기만큼 각 타일의 모기 개수를 입력받아 arr에 저장한다. dp 첫 행을 arr 첫 행 값으로 저장하고 다음 행부터 위, 왼쪽 대각선 위, 오른쪽 대각선 위를 살펴보며 최댓값으로 업데이트한다. 

 

최종 마지막 행 값 중에서 최댓값을 찾아 출력한다. 

---

---