[C++] 프로그래머스 '정수 삼각형' 풀이

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    /* 0/0,1/0,1//1,2/0,1 1,2 2,3 3,4*/
    int siz=triangle.size();
    vector<int> candidate(siz);
    for(int i=0;i<siz;i++){
        //바깥 행 
        for(int j=0;j<triangle[i].size();j++){
            // 해당 triangle[i][j]를 어디부터 어디까지 넣을 것인지 
            int cnt=siz-i;
            for(int k=j;cnt>0;cnt--) {candidate[k]+=triangle[i][j]; k++;}
        }
    }
    for(int e:candidate) { if(e>answer) answer=e; }
    return answer;
}

 dp 문제 

뭐지.. 왜 결괏값이 다를까 

무슨 조건을 빼먹었을까 

아 생각났다 

지금 저 식은 좀 겹쳐져 있도록 계산됨(?) 

#include <string>
#include <vector>
#include <bits/stdc++.h> 

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    /* 0/0,1/0,1//1,2/0,1 1,2 2,3 3,4*/
    int siz=triangle.size();
    vector<vector<int>> candidate(siz);
    candidate[0].push_back(triangle[0][0]);
    for(int i=1;i<siz;i++){
        //바깥 행 
        for(int j=0;j<triangle[i].size();j++){
            // 윗줄에 있는 요소들 하나씩 꺼내서 현재 요소 더해준 다음 insert 
            if(j!=0) candidate[i].push_back(candidate[i-1][j-1]+triangle[i][j]);
            candidate[i].push_back(candidate[i-1][j]+triangle[i][j]);
        }
    }
    for(int e:candidate[siz-1]) { if(e>answer) answer=e; }
    return answer;
}

딱 문제에 준 TC만 통과함.. 

ㅜㅜ 또 왜일까 

#include <string>
#include <vector>
#include <bits/stdc++.h> 

using namespace std;

int solution(vector<vector<int>> triangle) {
    ios::sync_with_stdio(0);
    int answer = 0;
    /* 0/0,1/0,1//1,2/0,1 1,2 2,3 3,4*/
    int siz=triangle.size();
    vector<vector<int>> candidate(siz);
    candidate[0].push_back(triangle[0][0]);
    for(int i=1;i<siz;i++){
        //바깥 행 
        for(int j=0;j<triangle[i].size();j++){
            // 윗줄에 있는 요소들 하나씩 꺼내서 현재 요소 더해준 다음 insert 
            if(j==0){
                //첫번째 항일 때는 
                candidate[i].push_back(candidate[i-1][j]+triangle[i][j]);
            }else if(j==triangle[i].size()-1){
                candidate[i].push_back(candidate[i-1][j-1]+triangle[i][j]);
            }else{
                int tmp=(candidate[i-1][j-1]> candidate[i-1][j])? candidate[i-1][j-1] : candidate[i-1][j];
                candidate[i].push_back(tmp+triangle[i][j]);
            }
        }
    }
    for(int e:candidate[siz-1]) { if(e>answer) answer=e; }
    return answer;
}

음 세 가지 경우의 수 (가장 왼쪽에 있을 때, 가장 오른쪽에 있을 때, 둘 다 아닐 때)를 생각해서 각각마다의 최댓값만 저장한다는 점이 다르다.