숫자삼각형 문제풀이

1. 소스 코드

백준 https://www.acmicpc.net/problem/1932 문제 정리. 

처음에는 Tree로 착각해서 Tree를 배열로 변환해서 처리하는 Heap 구조를 많이 생각했는데, 이상한 쪽으로 빠져서 해메다가 다른 분들이 푼 풀이를 보고 나름 정리했다.

입력을 받으면서 처리하도록 하여 메모리 사용을 최소화했다.

#include <iostream> int max = -1; int sum[501][501]; int main() { int N; int data; std::cin >> N; // get root value std::cin >> data; sum[0][0] = data; for(int y = 1; y < N; y++) { for(int x = 0; x <= y; x++) { std::cin >> data; if(x == 0) { sum[y][x] = sum[y-1][x] + data; } else if(x == y) { sum[y][x] = sum[y-1][x-1] + data; } else { sum[y][x] = std::max(sum[y-1][x-1], sum[y-1][x]) + data; } if(max < sum[y][x]) { max = sum[y][x]; } } } std::cout << max << std::endl; return 0; }

2. 동작

정상동작