프로그래머스 땅따먹기 JAVA

코딩테스트 연습 - 땅따먹기

문제

해당 문제는 2차원 배열이 주어졌을 때 1행부터 내려가면서 총합의 최댓값을 구하는 문제다. 단 같은 열을 연속으로 밟을 수는 없다.

조건

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

풀이

해당 문제는 dp를 이용하였고 문제를 보자마자 dp가 생각났다. 방법은 심플하다 먼저 첫 번째 행은 그냥 dp 배열에 똑같이 넣어주고 이후 행부터는 지금 자리에 들올 수 있는 가장 최댓값을 dp배열에 넣어주는 방식으로 dp 배열을 완성한 뒤 마지막 행에 대해서 최댓값을 결과에 넣고 리턴해주면 된다.

코드

class Solution {
static int solution(int[][] land) {
		int answer = 0;
		int[][] dp = new int[land.length][land[0].length];
		
		dp[0] = land[0]; // 첫번째 행은 입력데이터를 그대로 가져옴
		for (int i = 1; i < dp.length; i++) { // 이후부터는 이전행 데이터들과 자기 자신의 숫자를 더한값중 최대값을 저장 
			for (int j = 0; j < dp[0].length; j++) {
				for (int k = 0; k < dp[0].length; k++) {
					if(j == k) // 같은 열일경우 다음으로
						continue;
					dp[i][j] = Math.max(land[i][j] + dp[i-1][k], dp[i][j]);
				}
			}
		}
		for (int i = 0; i < dp[0].length; i++) { // 마지막 행에서 최대값을 찾아서 저장
			answer = Math.max(answer, dp[dp.length-1][i]);
		}
		
		return answer;
	}
}

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드