궤도

문제 풀이 이 문제도 동적계획법의 대표적인 문제 중 하나이다. 대표적인 풀이법에는 위에서 아래로 내려가는 방법과 아래에서 위로 올라가는 방법이 있는데, 후자가 훨씬 코드를 간단하게 짤 수 있다. i번째 줄을 계산한다고 하자. i번째 줄의 0번째(지금은 3)를 갱신하려면 i+1번째 줄의 0번째(7)와 더하거나 i+1번째 줄의 1번째(6)와 더하거나 이다. 둘 중 더 큰 값을 취하면 된다. 일반화하면 i번째 줄의 j번째 값을 갱신하려면 i+1번째 줄의 j번째 값과 i+1번째 줄의 j+1번째 값을 비교해 더 큰 값과 더하면 되는 것이다. 이를 n-1번째줄부터 1번째 줄까지 반복한 뒤 1번째 줄의 1번째 값을 리턴하면 된다. 소스코드 #include #include using namespace std; int ..