[programmers] 땅따먹기

문제
https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

 

---

< 땅따먹기 >

 

문제 풀이 (Java)

class Solution {
	int solution(int[][] land) {
		int answer = 0;

		int[][] sum = new int[land.length][4];

		for (int i = 0; i < 4; i++) {
			sum[0][i] = land[0][i];
		}

		for (int i = 1; i < land.length; i++) {
			for (int j = 0; j < 4; j++) {

				for (int k = 0; k < 4; k++) {
					if (j == k) {
						continue;
					}
					sum[i][j] = Math.max(sum[i][j], land[i][j] + sum[i - 1][k]);
				}
			}
		}

		for (int i = 0; i < 4; i++) {
			answer = Math.max(answer, sum[land.length - 1][i]);
		}

		return answer;
	}
}

 

합을 구하기 위해 sum 배열을 선언한다. 첫 행은 land 값 그대로 저장한다. 다음 행부터 탐색하며 같은 열이 아닌 윗행과 합이 최댓값일 때를 찾아 저장한다. 최종 sum 배열의 마지막 행 중에서 최댓값을 answer에 저장한 후 answer을 반환한다.

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges