[C++] 프로그래머스 정수 삼각형

문제 접근법 처음엔 트리로 생각해서 풀려고 했다. 부모노드 인덱스는 자식노드 인덱스에 2를 나눈 값임을 활용하여, 점화식을 세워 으로 풀려고 했다.

하지만, 트리구조와 비슷해도 트리가 아니였다... (너무 당연한 얘기) 문제를 풀때 자식노드의 입장에서, "부모 노드의 인덱스를 어떻게 구하면 좋지?

자식 노드 나누기 2 인가? 아니면, 자식 노드 빼기 level?"

이런식으로 사고가 좁혀져서 시간을 소모했다. 답은 간단했다.

부모 노드의 입장에서 생각하면 됐다. 부모 노드는 각각 두 개의 가지를 친다.

이를 활용하여 다음의 식을 생각했다. for i = 0 ~ level dp[level][i] = dp[level][i+1] = 여기서 중복되는 dp 값은 max로 처리해주면 됐다. 소스 코드 #include #include #include #define max(a,b) ((a)>(b)?

(a):(b...