1932
-
[백준] 1932번 정수 삼각형알고리즘/백준 2021. 8. 18. 19:17
문제 링크 풀이 이차원 배열도 일차원 배열처럼 연속된 메모리에 지나지 않지만 개발자가 작업할 때는 직관적으로 접근할 수 있어서 편합니다. 이 문제를 이차원 배열로 풀면 조금 편합니다. 예제로 주어진 입력값을 이차원 배열을 이용해 다음처럼 할 수 있습니다. 이 배열은 점화식을 위한 이차원 배열이며 dp[3][2]는 [3][2] 위치까지 합산된 최대값을 표현합니다. 즉 dp[2][1]과 dp[2][2]를 비교해서 더 큰 값을 [3][2]의 좌표의 값과 더해서 dp[3][2]를 갱신하면 됩니다. 점화식은 다음과 같습니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j] 반복문 사용을 최소화하기 위해 triangle 이차원 배열을 선언하지 않고 일차원 배열을 하..