[BOJ] 1932번 : 정수 삼각형
2024. 9. 1. 12:56ㆍAlgorithm
1. problem :
https://www.acmicpc.net/problem/1932
2. solution 1 :
#include <bits/stdc++.h>
using namespace std;
int n;
int d[505][505];
int trees[505][505];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
int depth = 0;
for (int i = 1; i <= n; i++) { // 층을 표현;
depth++;
for (int j = 1; j <= depth; j++) cin >> trees[i][j]; // 각 층의 몇번째 가지인지 표현;
}
d[1][1] = trees[1][1], d[2][1] = trees[2][1] + d[1][1], d[2][2] = trees[2][2] + d[1][1];
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j == 1) d[i][j] = d[i - 1][j] + trees[i][j];
else if (j == i) d[i][j] = d[i - 1][j - 1] + trees[i][j];
else d[i][j] = max(d[i - 1][j - 1], d[i - 1][j]) + trees[i][j];
}
}
int maxVal = 0;
for (int i = 1; i <= n; i++) {
if (maxVal < d[n][i]) maxVal = d[n][i];
}
cout << maxVal << '\n';
}
3. solution 2:
// Authored by : Hot6Mania
// Co-authored by : -
// http://boj.kr/b5c330a8f8684bca91511e8ea2a19a34
#include <bits/stdc++.h>
using namespace std;
int n;
int a[505][505], d[505][505];
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
cin >> a[i][j];
d[1][1] = a[1][1];
for(int i = 2; i <= n; ++i)
for(int j = 1; j <= i; ++j)
d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j];
cout << *max_element(d[n] + 1, d[n] + n + 1);
}
source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/1932.cpp
basic-algo-lecture/0x10/solutions/1932.cpp at master · encrypted-def/basic-algo-lecture
바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.
github.com
'Algorithm' 카테고리의 다른 글
[BOJ] 2193번 : 이친수 (0) | 2024.09.01 |
---|---|
[BOJ] 11727번 : 2 x n 타일링 2 (1) | 2024.09.01 |
[BOJ] 1003번 : 피보나치 함수 (2) | 2024.09.01 |
[BOJ] 12852번 : 1로 만들기 2 (0) | 2024.08.31 |
[BOJ] 11659번 : 구간 합 구하기 4 (0) | 2024.08.31 |