백준 1932 자바

백준 1932번 DP 문제

문제 사이트

• 해설

  • 제일 위에서 부터 제일 아래까지 내려가면서 자기 자식을 더해서 가장 큰 값을 구하는 문제이다.

    

    i가 1->3으로 갈 떄까지 최고 합을 구하면 되는 것입니다. 경우의 수를 보게 되면 ABD / ABE / ACE / ACF 이렇게 4가지가 있다. ABF가 안되는 이유는 당연히 문제에 대각선 왼/오른쪽(자식) 중 선택하라고 했으므로 F는 C의 자식이지 B의 자식이 아니기 떄문에 안된다.

    

    간략하게 배열에 맞게 숫자를 넣어봤다. 그럼 이제 하나씩 더해 보도록 하겠다. 빨강 테두리 부분과 파랑 테두리 부분을 먼저 보면 이 부분의 합을 구하는 방법은 딱 하나 밖에 없다. 예를 들어 (3,1) 까지 더한 값을 구하기 위해서 (3,1) + (1,1) +.(2,1) 이렇게 밖에 하지 못한다. (4,1)은 (3,1)까지 더한 값에 (4,1)까지 더한 값이 되겠다.

    그리고 파랑 테두리 부분은 (4,4)를 구하기 위해서 (1,1) + (2,2) + (3,3) + (4,4)가 된다. 그러면 !!! 이걸 (i , j)라고 바꾼다면 빨강 테두리는 j의 값을 변하지 않고 1로 고정되어 있으며 파랑 테두리는 i와 j의 값이 같다. 그러면 다음과 식이 같다.

    if(i == 1)
    list[i][j] = list[i-1][j] + list[i][j];

    위에 식은 빨간 테두리에 값을 구하는 것이다. Ex) (2,1) = (1,1) + (2,1)이 된다.

    if(i == j)
    list[i][j] = list[i-1][j-1] + list[i][j];

    위에 식은 파란 테두리에 값을 구하는 것이다. Ex) (2,2) = (1,1) + (2,2)이 된다

  • 이제 중간 값을 구하기 위해서 비교가 필요하다.

    • 우리가 (3,2) 값 까지 더하려면 (2,1) / (2,2) 둘 값을 비교하여 더 큰 값과 합을 구해야한다.

      list[i][j] = Math.max((list[i-1][j-1] , list[i-1][j]) + list[i][j]);

      중간 값을 구하기 위해선 위에 식 처럼 사용가능하다. (3,2) = Math.max((2 , 1), (2 , 2) + (3, 2))