프로그래머스 정수 삼각형

 

예전에 수업시간에 풀어봤던 문제랑 같았다.

그때는 2차원 배열로 구현했었는데, 이제 프로그래머스 환경에 익숙해지고자

2차원 벡터로 그대로 구현해보았다.

 

#define MAX(a, b) ((a >= b)?a:b)

int solution(vector<vector<int>> triangle) {
    
    int answer = 0;
    int height = triangle.size();
    
    for(int i = 1; i < height; i++) {
        
        for(int j = 0; j <= i; j++) {
            
            // left = i - 1, j - 1
            // right = i - 1, j
            
            int left = ((j == 0) ? 0 : triangle[i - 1][j - 1]);
            int right = ((j == i) ? 0 : triangle[i - 1][j]);

            triangle[i][j] = MAX(left, right) + triangle[i][j];

            answer = MAX(answer, triangle[i][j]);
            
        }
    
    }

    return answer;
}

 

초반에 조금 헤매서 시간을 많이 잡아먹었다.

 

 

 

 

+ 추가로, 2차원 벡터의 복사가 갑자기 궁금해져서 찾아본 뒤 구현해봤다.

    vector<vector<int>> x = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
    
    vector<vector<int>> z(5, vector<int>(5, 0));
    
    
    copy(x.begin(), x.end(), z.begin());
    
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            
            cout << z[i][j] << " ";
        }
        cout << "\n";
        
    }

문제에서의 입력 그대로 이용했고, n x n 벡터가 아닌터라

 

빈 공간은 0으로 채운 벡터를 선언한 뒤에

copy 함수를 이용했다.

 

---

start at 13 : 30

end at 13 : 54