[백준] 1932번: 정수 삼각형

1932번: 정수 삼각형

DP 문제의 기초 중의 기초!

 

귀찮게 풀면 귀찮게 풀 수도 있겠지만 일단 알고리즘 문제 풀이니 간단한 방식으로 풀었습니다.

 

이런 문제 같은 경우에 메모리를 조금 낭비하면 특별히 범위 체크 없이 문제를 풀 수 있는데,

저는 이번 풀이에서 전역 변수로 배열을 선언하고, 그 배열들은 0으로 초기화되어 있는 상태이니 그 상태에서 DP를 적용했습니다.

 

사실 DP 문제를 조금 쉽게 풀 수 있는 팁은 index에 접근할 때 0부터 접근하지 않고, 1부터 접근하는 것입니다.

1부터 접근하게 될 경우 이전 index에 접근할 때 생기는 귀찮은 오류를 막을 수 있어서 편리합니다.

 

뭐, 알고리즘 문제는 빠르고 정확하게 푸는 게 핵심이기 때문에 메모리 조금 더 쓰는 정도는 일반적으로 괜찮다고 합니다.

 

이전 row에 접근해서 그 row에 있는 왼쪽, 오른쪽 col을 검사한 후 큰 값을 더해주면 현재 index까지의 max 값을 얻을 수 있게 됩니다.

이렇게 한 다음 마지막 row에 저장된 값 중 max 값을 찾으면 그 값이 답이 됩니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

#define ADDITIONAL 5

int N;
int triangle[500 + ADDITIONAL][500 + ADDITIONAL];
int maxSumRoute[500 + ADDITIONAL][500 + ADDITIONAL];
int ans = 0;

void input() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);

  cin >> N;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
      cin >> triangle[i][j];
    }
  }
}

bool rangeCheck(int st, int ed, int target) {
  if (st <= target && target <= ed) {
    return true;
  }
  return false;
}

void dp() {
  
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
      maxSumRoute[i][j] = triangle[i][j];
      
      if (i == 1) {
        continue;
      }

      maxSumRoute[i][j] += max(maxSumRoute[i - 1][j - 1], maxSumRoute[i - 1][j]);

      if (i == N) {
        if (ans < maxSumRoute[i][j]) {
          ans = maxSumRoute[i][j];
        }
      }
    }
  }
}

void printAnswer() {
  cout << ans << '\n';
}

int main() {

  input();
  dp();
  printAnswer();

  return 0;
}