백준 1932번: C++

https://www.acmicpc.net/problem/1932

문제 탐색

숫자 이동은 대각선으로만!

현재 위치: n
이동 가능 위치 : 2n or 2n + 1

 

n 레벨에 도달하는 가장 최대 합을 구해야 한다

 

바텀업이 더 직관적이라는 생각

bcs 탑다운 같은 경우 쭉 내려왔다가~ 다시 위로 가서 고민해야하니까 뭔가 복잡하다는 생각이 든다!

 

이 문제에서는 바텀업으로 해보겠습니다~~

 

필요한 식

1. 배열 입력

for(int i = 0; i< n;i++){
    for(int j = 0; j< i+1; j++){
      int a;
      cin >> a;
      tri[i][j] = a;
    }
  }

2차원 배열로 입력 받았습니다.

 

2. 밑에서부터 올라가기

for(int i = n-1 ; i >= 1 ; i--){
    for(int j = 0; j< i+1; j++){
      tri[i-1][j] += max(tri[i][j], tri[i][j+1]);
    }
  }

(i, j) 의 위치라고 할 때

(i-1, j)=> 한줄 위의 위치

의 값은

max(tri[i][j], tri[i][j+1])

나랑 내 옆에 값 중에 더 큰 값을 현재 값에 더한다!

 

그렇게 올라가다보면~,,,,주어진 레벨까지의 최대합 구하기 가능!

최종 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
  int dp[501];
  int n;

  cin >> n;

  int tri[501][501];

  for(int i = 0; i< n;i++){
    for(int j = 0; j< i+1; j++){
      int a;
      cin >> a;
      tri[i][j] = a;
    }
  }

  for(int i = n-1 ; i >= 1 ; i--){
    for(int j = 0; j< i+1; j++){
      tri[i-1][j] += max(tri[i][j], tri[i][j+1]);
    }
  }

  cout << tri[0][0] << endl;

  
return 0;

}

첨에 

tri 배열 크기 지정을 안해줬더니 segment fault가 떴다!

이러한 코딩 테스트 문제에서는 범위 지정해주고 푸는 것이 좋다~.... 그닥 메모리 오바되지 않는담~!