Dynamic Programming2 [프로그래머스][C++] 정수 삼각형 #include #include using namespace std; int solution(vector triangle) { int answer = 0; for (int i = triangle.size() - 1; i > 0; i--) { for (int j = 0; j < triangle[i].size() - 1; j++) { // 하위 두개의 원소 중 큰 원소를 윗단 원소에 더해줌 int left = triangle[i][j]; int right = triangle[i][j + 1]; triangle[i - 1][j] += max(left, right); } } answer = triangle[0][0]; // root 노드의 값이 최대값이 됨 return answer; } 1. 삼각형의 가장 밑의.. 2023. 8. 8. [백준 1463번][C++] 1로 만들기 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { // 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; vector dp(N + 1); // 2 -> 1 => 1 // 3 -> 1 => 1 // 4 -> 2 or 4 -> 3 => 1 + dp(2) or 1 + dp(3) // 5 -> 4 => 1 + dp(4) // 6 -> 3 or 6 -> 2 .. 2023. 8. 7. 이전 1 다음
