2017-03-16 알고리즘 문제 풀기

숫자삼각형

---

[백준] 계단오르기 1932번

#include<stdio.h> int max(int x, int y) { return x > y ? x : y; } int main() { int arr[501][501] = { 0 }; int n; int input; int ans = 0;  scanf("%d", &n); for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { scanf("%d", &input); arr[i][j] = max(arr[i - 1][j - 1], arr[i - 1][j]) + input; ans = max(ans, arr[i][j]); } } printf("%d\n", ans); return 0; }

예시를 통해서 분석했을 때,

arr[1][1] = 0 + 7  ------ ans = 7

arr[2][1] = 7 + 3  ------ ans = 10

arr[2][2] = 7 + 8  ------ ans = 15

arr[3][1] = 7 + 3 +8  ------ ans = 18 

arr[3][2] = 7 + 8 + 1 ------ ans = 18 

arr[3][2] = 7 + 8  + 0 ------ ans =  18

이런식으로 진행되어 

가장 쉬운 예를 이용해서 규칙을 찾아 보면 

arr[3][2] = max(arr[2][1],arr[2][2]) + input; 의 규칙이 도출될 수 있다.

이 방식을 이용해서 문제를 풀었습니다.