https://programmers.co.kr/learn/courses/30/lessons/43105?language=cpp
코딩테스트 연습 - 정수 삼각형
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30
programmers.co.kr
원래 'N으로 표현' 이란 문제를 먼저 풀고 싶었는데 그건 도저히 내 머리로는 아직 모르겠다....
DP는 너무 어렵다....
소스코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int height;
vector<vector<int>> vertex;
vector<vector<int>> tri;
void dfs(int depth) {
//모든 행을 다 담은 경우 return
if(depth == height) return;
vector<int> v(depth+1,0);
for(int i = 0; i<depth ; i++) {
//좌,우 번갈아서 아래행의 최대값 비교해 변경해주기
if(v[i] < vertex[depth-1][i]+tri[depth][i]) v[i] = vertex[depth-1][i]+tri[depth][i];
if(v[i+1] < vertex[depth-1][i]+tri[depth][i+1]) v[i+1] = vertex[depth-1][i]+tri[depth][i+1];
}
//최댓값을 저장한 배열을 최댓값 이중배열인 vertex에 저장
vertex.push_back(v);
//다음 깊이로 dfs 실행
dfs(depth+1);
}
int solution(vector<vector<int>> triangle) {
int answer = 0;
tri = triangle;
height = triangle.size();
vertex.push_back(triangle[0]);
//다음 연산할 행인 1부터 dfs 시작
dfs(1);
//최댓값 이중 배열의 마지막 행 반환
vector<int> v_ans = vertex[height-1];
//sort로 배열 정렬(오름차순) 후 맨 뒤 원소를 answer에 저장
// 맨 뒤 원소가 가장 큰 값을 가지고 있음.
sort(v_ans.begin(),v_ans.end());
answer = v_ans.back();
return answer;
}
'CodingTest Practice > Programmers' 카테고리의 다른 글
프로그래머스 : 우유와 요거트가 담긴 장바구니 (SQL, ORACLE) (0) | 2022.06.10 |
---|---|
프로그래머스 : 헤비 유저가 소유한 장소 (SQL, ORACLE) (0) | 2022.06.10 |
프로그래머스 : N-Queen (C++, Lv.3, 백트래킹) (0) | 2022.06.09 |
프로그래머스 : 배달 (C++, Lv.2, 다익스트라) (0) | 2022.06.07 |
프로그래머스 : String, Date (SQL, ORACLE) (0) | 2022.06.06 |