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

문제 접근법 처음엔 트리로 생각해서 풀려고 했다. 부모노드 인덱스는 자식노드 인덱스에 2를 나눈 값임을 활용하여, 점화식을 세워 <dp[i] = dp[i/2] + 상수값>으로 풀려고 했다. 하지만, 트리구조와 비슷해도 트리가 아니였다... (너무 당연한 얘기) 문제를 풀때 자식노드의 입장에서, "부모 노드의 인덱스를 어떻게 구하면 좋지? 자식 노드 나누기 2 인가? 아니면, 자식 노드 빼기 level?"이런식으로 사고가 좁혀져서 시간을 소모했다. 답은 간단했다. 부모 노드의 입장에서 생각하면 됐다. 부모 노드는 각각 두 개의 가지를 친다. 이를 활용하여 다음의 식을 생각했다. for i = 0 ~ level dp[level][i] = dp[level][i+1] = 여기서 중복되는 dp 값은 max로 처리해주면 됐다. 소스 코드 #include <string> #include <vector> #include <iostream> #define max(a,b) ((a)>(b)?(a):(b...

원문링크 : [C++] 프로그래머스 정수 삼각형