1932 (1) 썸네일형 리스트형 [BOJ][DP] 1932. 숫자삼각형 https://www.acmicpc.net/problem/1932 DP 문제다. 문제에서 우리가 잡아내야 할 포인트는 1. 이제까지 선택된 수의 합이 최대가 되는 경로.2. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼/오 중 하나를 선택. 점화식을 세우기 위해서 일단 이해를 해보자. 문제에서는 수들을 삼각형의 형태로 나타내었지만, 어렵게 생각할 필요가 없다.위에서부터 차례대로 배열에 넣어주면 아래와 같다. 그럼 여기서 어떻게 어떠한 값에 대한 왼/오 대각선 값을 가리킬 수 있을까? 보다시피 한 값의 인덱스 +2 = L, +3 = R 이 되는것을 알 수있다. 얼추 이해가 오기 시작하는가?그렇다면 이제 여태까지 이해한 것을 바탕으로 점화식을 세워보자.(arr은 입력받았던 값을 저장해둔 배열이다.).. 이전 1 다음
