📝 문제

처음에는 그래프 탐색과 비슷하게 생각해서 dfs알고리즘으로 풀었다.
하지만 위의 방법으로 풀면 시간초과가 난다.
dfs의 시간복잡도는 정점의 개수(N)에 대하여 O(N^2)이라서 그런 거 같다.
근데 1억에 1초니까 N^2하면 최악의 경우가 250,000인데...
흠,, 왜 시간초과가 나는 걸까?
그래서 다른 풀이법을 고민해보다가 수를 입력 받을 때 바로 DP로 풀면 시간초과를 피할 수 있을 거 같았다.
DP로 풀 때는 입력과 동시에 계산을 하므로 시간복잡도는 O(N)이 된다.

📌 코드

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1932 {

  /**
   * dfs로 푸니까 시간초과
   * dp로 풀어보자
   */

  static int n;
  static int[][] tree;
  static int answer = 0;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    tree = new int[n][n];
    StringTokenizer st;
    tree[0][0] = Integer.parseInt(br.readLine());
    for(int i = 1; i < n; i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0; j <= i; j++){
        // prev : tree[i-1][j] or tree[i-1][j-1]
        int input = Integer.parseInt(st.nextToken());
        // col : 0
        if(j == 0){
          tree[i][j] = tree[i-1][j] + input;
        }
        else if(j == i){
          tree[i][j] = tree[i-1][j-1] + input;
        }
        else{
          tree[i][j] = Math.max(tree[i-1][j], tree[i-1][j-1]) + input;
        }
      }
    }
    for(int i : tree[n-1]){
      answer = Math.max(answer, i);
    }
    System.out.println(answer);
  }
}