프로그래머스-정수 삼각형

문제 링크

1. 문제 접근 과정🧐

1. 문제의 그림은 삼각형으로 되어 있지만 실제 입력은 그렇게 되어 있지 않다는 것을 고려
2. 제일 왼쪽은 본인의 오른쪽 위만 접근 가능하고 제일 오른쪽은 본인의 왼쪽 위만 접근 가능함
3. 양쪽 끝을 제외한 중간 부분은 왼쪽, 오른쪽 위 모두 체크해야 함
4. 계산을 마치면 모두 0이상이기에 제일 끝의 합 중 가장 큰 수가 정답이 됨
   
   

2. 시행착오🤯

• 처음에 문제를 풀 때 잘못 생각하여 본인의 위와 양 옆을 체크하여 실패했다.
  
• 오답 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int s = triangle.size();
    vector<vector<int>> dp(s + 1, vector<int>(s + 1, 0));
    dp[1][1] = triangle[0][0];
    for(int i = 1; i < s; i++){
        for(int j = 0; j < triangle[i].size(); j++){
            dp[i + 1][j] = max(dp[i][j], max(dp[i][j - 1], dp[i][j + 1])) + triangle[i][j];
        }
    }
    for(int i = 0; i < s; i++){
        answer = max(answer, dp[s - 1][i]);
    }
    return answer;
}

3. 개선한 코드😄

• 조건을 좀 더 생각하여 문제 접근 방법에서 말했듯 양쪽 끝과 중간 부분을 각각 계산하여 해결
  
• 정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int s = triangle.size();
    vector<vector<int>> dp(s + 1, vector<int>(s + 1, 0));
    dp[0][0] = triangle[0][0];
    for(int i = 1; i < s; i++){
        for(int j = 0; j < triangle[i].size(); j++){
            if(j == 0) dp[i][j] = dp[i - 1][j] + triangle[i][j];
            else if(j == triangle[i].size() - 1) dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
            else dp[i][j] = max(dp[i -1][j -1], dp[i - 1][j]) + triangle[i][j];
        }
    }
    for(int i = 0; i < s; i++){
        answer = max(answer, dp[s - 1][i]);
    }
    return answer;
}

4. 회고💭

• 문제를 접근할 때 다양한 케이스를 생각해서 조건을 잘 고려해야 한다.
• 먼저 수학 문제 풀듯이 풀어보고 코드로 구현하는 것도 도움이 될 거 같다.