[Epper] 정수삼각형 java 자바

문제

 

풀이

문제에서 힌트를 줬듯이..ㅋㅋㅋㅋ dp를 이용하여 풀면 된다.

dp를 초기화해주어야 하는데 가장 밑의 층을 입력받은 배열 값들로 초기화해준 후 시작한다.

solution 함수에서는 인덱스 값 i, j를 파라미터로 받고

해당 인덱스의 dp 값이 0일 경우에 연산을 진행한다.

 

이때 아직 의문인 게.. i==n-1일 경우에 dp[i][j]를 return해주도록 작성을 해야 정답이 맞다고 나오는데 이미 초기화를 해주어서 상관 없는 거 아닌가 했는데.... 아닌가보다......

모범 답안 나오면 그때 다시 확인해보는 걸로...

 

코드

package Level3;
import java.util.Scanner;
public class E14No9_정수삼각형 {
	
	static int[][]dp;
	static int[][]arr;
	static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		dp=new int[n][n];
		arr=new int[n][n];
		
		//삼각형 입력 
		for(int i=0;i<n;i++) {
			for(int j=0;j<=i;j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		
		//dp 시작점 초기화 
		for(int i=0;i<n;i++) {
			dp[n-1][i]=arr[n-1][i];
		}
		
		System.out.println(solution(0,0));
	}
	
	static int solution(int i, int j) {
		if(i==n-1) {
			return dp[i][j];
		}
		
		if(dp[i][j]==0) {
			dp[i][j]=arr[i][j]+Math.max(solution(i+1, j+1), solution(i+1, j));
		}
		
		return dp[i][j];
	}

}