[백준]동적 계획법1/정수 삼각형/1932 풀이 JAVA

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

풀이 (JAVA)

원래는 dp를 Integer가 아니라 int로 선언했었다.

(그랬더니 메모리는 덜 잡았고 시간은 똑같이 걸렸다.)

그런데 int형으로 하면 디폴트가 0인데,

맨 아래층 값이 모두 0일 수도 있기 때문에...

디폴트 값이 null인 Integer배열을 써야 맞을 거 같다.

---

문제를 딱 보고 아 이렇게 하면 되겠다...! 라는 느낌이 오랜만에 들었다.

근데... 그 느낌이 틀렸다.ㅋ

좁은 시야로 보면 좁게 보기 쉬운 듯,,,

느낌을 코드로 짜는 것도 어려웠다...

문제 많이 풀어봐야지