[Algorithm] Programmers 땅따먹기

 

- 목차

 

소개.

"프로그래머스 땅따먹기" 문제의 웹 링크입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

 

 

문제 분석.

처음에는 해당 문제는 DFS 로 완전 탐색으로 해결하려고 시도하였습니다.

하지만 행의 갯수가 100,000 이기 때문에 완전 탐색을 시도하게 되면,

완전 탐색을 수행하게 되면 최악의 케이스로 N*N 의 시간복잡도를 가지게 됩니다.

따라서 해당 문제는 단순한 연산으로 접근해야합니다.

 

 

< DFS 로 시도한 코드 >

import java.util.Stack;

class Solution {
  public int solution(int[][] land) {
    int answer = 0;

    for (int x = 0; x < 4; x++) {
      int[][] copy = new int[land.length][land[0].length];
      for (int i = 0; i < land.length; i++) {
        for (int j = 0; j < land[0].length; j++) {
          copy[i][j] = land[i][j];
        }
      }

      Stack<int[]> stack = new Stack();
      int size = land[0].length;
      stack.push(new int[]{0, x});
      while (!stack.isEmpty()) {
        int[] position = stack.pop();
        int curY = position[0];
        int curX = position[1];

        for (int nextX = 0; nextX < size; nextX++) {
          if (curX == nextX) continue;
          int nextY = curY + 1;
          if (nextY >= land.length) continue;
          copy[nextY][nextX] = Math.max(copy[curY][curX] + land[nextY][nextX], copy[nextY][nextX]);
          stack.push(new int[]{nextY, nextX});
        }
      }

      for (int xx = 0; xx < 4; xx++) {
        if (answer < copy[land.length - 1][xx]) {
          answer = copy[land.length - 1][xx];
        }
      }
    }

    return answer;
  }
}

 

 

문제 풀이.

각 행의 값들 중 최댓값을 다음 행의 값에 더해줍니다.

아래와 합배열이 같은 접근법을 취해야 시간 복잡도 문제를 해결할 수 있습니다.

 

 

import java.util.*;

class Solution {
  int solution(int[][] land) {
    int answer = 0;
    for (int i = 0; i < land.length - 1; i++) {
        land[i + 1][0] += Math.max(Math.max(land[i][1], land[i][2]), land[i][3]);
        land[i + 1][1] += Math.max(Math.max(land[i][0], land[i][2]), land[i][3]);
        land[i + 1][2] += Math.max(Math.max(land[i][0], land[i][1]), land[i][3]);
        land[i + 1][3] += Math.max(Math.max(land[i][0], land[i][1]), land[i][2]);
    }
    
    for (int i = 0; i < 4; i++) {
        answer = Math.max(answer, land[land.length - 1][i]);
    }

    return answer;
  }
}