삼각형 위의 최대 경로 수 세기
-
TRIPATHCNT 삼각형 위의 최대 경로 수 세기 / ALGOSPOTALGOSPOT 2020. 2. 7. 14:59
문제링크 : https://algospot.com/judge/problem/read/TRIPATHCNT 제출링크 : https://algospot.com/judge/submission/detail/655903 자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/TRIPATHCNT/src/Main.java 2차원 DP를 2번 풀어야 하는 문제입니다. 첫번째 풀어야할 문제는 TRIANGLEPATH 문제에서 푼건 처럼, 누적합을 계산하고 dp_{i,j}에 저장합니다. 두번째 풀어야 할 문제가, 경로의 개수를 세는 문제입니다. (i, j)에서 경로의 개수를 세는 문제를 countPath(i, j) 라고 정의 하면, 아래 3가지 경우로, countPath(..