[문제풀이] B1932 정수삼각형

  🪅. 문제를 보고 DP를 생각하고, 구현할 수 있느냐 => 답을 구하는 과정을 일반화할 수 있느냐, 예외를 if문으로 처리할 수 있느냐
  🪅. 문제를 보는 시각을, 윗줄 데이터가 아랫줄 데이터를 선택하는 것이 아닌, 아랫줄 데이터가 윗줄 데이터 중 큰데이터를 선택하는 시각으로 볼 수 있느냐
  🪅. 역순으로 정렬하기 위해, int[]를 Integer[]로 변환할 수 있느냐

정수 삼각형

---

[시간초과로 통과 못한 코드.java]

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

  public class B1932_정수삼각형 {
      static int N;
      static List<Integer>[] tree;
      static boolean[][] isSelected;
      static int maxSum;

      public static void selectChild(int r, int node) {
          if(r == N) {
              int sum = 0;
              for(int i = 0; i < N; i++) {
                  for(int j = 0; j < tree[i].size(); j++) {
                      if(isSelected[i][j]) {
                          sum += tree[i].get(j);
                      }
                  }
              }
              if(sum > maxSum) {
                  maxSum = sum;
              }
              return;
          }

          if(r == 0) {
              isSelected[r][node] = true;
              selectChild(r+1, node);
              return;
          }

          isSelected[r][node] = true;
          selectChild(r+1, node);
          isSelected[r][node] = false;

          isSelected[r][node+1] = true;
          selectChild(r+1, node+1);
          isSelected[r][node+1] = false;
      }
      public static void solution() {
          selectChild(0,0);
      }
      public static void init() throws NumberFormatException, IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N = Integer.parseInt(br.readLine());
          tree = new ArrayList[N];
          for(int i = 0; i < N; i++) {
              tree[i] = new ArrayList<>();
          }
          isSelected = new boolean[N][500];

          StringTokenizer token;
          for(int i = 0; i < N; i++) {
              token = new StringTokenizer(br.readLine(), " ");
              for(int j = 0; j < i+1; j++) {
                  tree[i].add(Integer.parseInt(token.nextToken()));
              }
          }
      }
      public static void main(String[] args) throws NumberFormatException, IOException {
          init();
          solution();
          System.out.println(maxSum);
      }
  }

💡. 문제 접근 과정
: 처음에는 완전탐색문제(부분집합)인 줄 알았다.
하지만 한 줄마다 선택할 (문제의 조건을 만족하는)하나의 데이터를 고르는 과정이
삼각형의 크기가 최대 500이 되었을 때, 시간복잡도가 2의 500승이 되어버려 시간초과가 난다.

[통과한 코드.java]

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.List;
  import java.util.StringTokenizer;

  public class B1932_정수삼각형__ver2 {
      static int N;
      static List<Integer>[] tree;
      static int[][] M;
      public static int dp(int x, int y) {
          // 1 2 4 7 11
          if(x == 1) return M[1][0] = tree[1].get(0);
          if(y == 0) return M[x][0] = M[x-1][0] + tree[x].get(0);    
          if(M[x][y] != 0) return M[x][y];
          return M[x][y] = Math.max(M[x-1][y-1], M[x-1][y]) + tree[x].get(y);

      }
      public static void init() throws NumberFormatException, IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N = Integer.parseInt(br.readLine());
          tree = new ArrayList[N+1];
          M = new int[N+1][N];

          for(int i = 1; i < N+1; i++) {
              tree[i] = new ArrayList<>();
          }
          StringTokenizer token;
          for(int i = 1; i < N+1; i++) {
              token = new StringTokenizer(br.readLine(), " ");
              for(int j = 1; j < i+1; j++) {
                  tree[i].add(Integer.parseInt(token.nextToken()));
              }
          }
      }
      public static void main(String[] args) throws NumberFormatException, IOException {
          init();

          for(int i = 1; i < N+1; i++) {
              for(int j = 0; j < i; j++) {
                  dp(i,j);
              }
          }

          Integer[] resultWrapper = Arrays.stream(M[N]).boxed().toArray(Integer[]::new);
          Arrays.sort(resultWrapper, Comparator.reverseOrder());
          System.out.println(resultWrapper[0]);
      }
  }

💡. 문제 접근 과정
: 삼각형을 이루는 각 줄에서의 (맨 위에서 시작해서) 각 데이터까지의 합을 구하면 되겠다는 생각이 들었고,
그 합을 구하는 과정이 '윗 줄의 (조건을 만족하는)두 개의 데이터' 중에서 '큰 값'과 더하면 되겠다고 생각했다.
즉, 작은 값부터 답을 구하고 기록해 둔 후, 이를 이용하는 '메모이제이션(dp)'을 이용하면 되겠다고 생각했다.
결국, 마지막 줄에서 최대값을 찾아 출력하면 그게 답이된다.