728x90
유형 | 난이도 | 완료일 | 링크 | 특이사항 |
DP | 실버1 | 23/02/19 | https://www.acmicpc.net/problem/1932 |
내 코드
#include <iostream>
#include <algorithm>
using namespace std;
int arr[501][501];
int n;
int main(void)
{
cin >> n;
for(int i=0; i<n; i++)
{
for(int j=0; j<=i; j++)
{
cin >> arr[i][j];
}
}
for(int i=n-2; i >= 0; i--)
{
for(int j=0; j<=i; j++ )
{
arr[i][j]+= max(arr[i+1][j],arr[i+1][j+1]);
}
}
cout << arr[0][0];
}
앞서 고생해서 푼 ‘RGB거리’ 문제와 비슷한 점이 있어 쉽게 해결했다.
삼각형의 맨 밑에서부터 반복문을 돌렸다. arr[i][j]와 arr[i][j+1] 중 더 큰 값을 arr[i-1][j]에 더해가면서 누적 합을 구하는 방식으로 계산했고, 결국 마지막엔 삼각형 꼭대기의 하나의 숫자만 남아 arr[0][0]에 최댓값이 저장된다.
쉽게 금방 풀려서 뿌듯했다.
728x90
'Algorithm' 카테고리의 다른 글
[백준/C++] 10844 쉬운 계단 수 (S1) (0) | 2023.10.16 |
---|---|
[백준/C++] 2579 계단 오르기 (S3) (0) | 2023.10.15 |
[백준/C++] 1149 RGB거리 (S1) (1) | 2023.10.15 |
[백준/C++] 1912 연속합 (S2) (1) | 2023.10.15 |
[백준/C++] 94671 파도반 수 (S3) (0) | 2023.10.15 |