문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
int solution(int[][] land) {
    for (int i = land.length - 2; i >= 0; i--) {
        int rowIndex = i + 1;
        land[i][0] += max(land[rowIndex][1], max(land[rowIndex][2], land[rowIndex][3]));
        land[i][1] += max(land[rowIndex][0], max(land[rowIndex][2], land[rowIndex][3]));
        land[i][2] += max(land[rowIndex][0], max(land[rowIndex][1], land[rowIndex][3]));
        land[i][3] += max(land[rowIndex][0], max(land[rowIndex][1], land[rowIndex][2]));
    }

    int answer = max(land[0][0], max(land[0][1], max(land[0][2], land[0][3])));
    return answer;
}

흐름

  1. 마지막 행 전행 부터 반복문을 시작해서 i가 0이 될 때까지 반복한다.
  2. i행의 각 인덱스에는 자기 자신의 열을 제외한 이전 행의 값 중 가장 큰 값과 자기 자신의 값을 더한 값을 저장한다.
  3. 위 과정을 반복하면 0번째 행들의 index에 계산된 값들이 할당되어 있을 테니
  4. 0 번째 행 중에서 가장 큰 값을 return한다.
  5. 끝

결과

정확성

번호 속도
테스트 1 통과 (1.05ms, 51.1MB)
테스트 2 통과 (1.16ms, 52.7MB)
테스트 3 통과 (1.16ms, 50.8MB)
테스트 4 통과 (1.18ms, 53MB)
테스트 5 통과 (1.18ms, 52.7MB)
테스트 6 통과 (1.14ms, 52.9MB)
테스트 7 통과 (1.18ms, 51.4MB)
테스트 8 통과 (1.13ms, 52.7MB)
테스트 9 통과 (1.25ms, 53.3MB)
테스트 10 통과 (1.21ms, 50.7MB)
테스트 11 통과 (1.18ms, 52.4MB)
테스트 12 통과 (4.25ms, 52.5MB)
테스트 13 통과 (1.19ms, 53.2MB)
테스트 14 통과 (1.16ms, 53.1MB)
테스트 15 통과 (1.19ms, 51MB)
테스트 16 통과 (1.16ms, 52.5MB)
테스트 17 통과 (1.14ms, 55.3MB)
테스트 18 통과 (1.16ms, 52.2MB)

효율성

번호 속도
테스트 1 통과 (28.10ms, 94.3MB)
테스트 2 통과 (28.01ms, 95.7MB)
테스트 3 통과 (25.28ms, 97.6MB)
테스트 4 통과 (25.93ms, 101MB)

테스트 케이스

1
2
3
4
5
6
7
8
assertEquals(16, test.solution(new int[][] {{1,2,3,5},{5,6,7,8},{4,3,2,1}}));
assertEquals(20, test.solution(new int[][] {{4, 3, 2, 1}, {2, 2, 2, 1}, {6, 6, 6, 4}, {8, 7, 6, 5}}));
assertEquals(115, test.solution(new int[][] {{1, 2, 3, 5}, {5, 6, 7, 8}, {4, 3, 2, 1}, {100, 0, 9, 8}}));
assertEquals(33, test.solution(new int[][] {{1, 2, 3, 5}, {10, 11, 12, 11}, {16, 15, 13, 13}}));
assertEquals(409, test.solution(new int[][] {{1, 100, 15, 3}, {1, 2, 3, 4}, {100, 99, 98, 97}, {97, 98, 99, 100}, {4, 3, 2, 1}, {100, 100, 100, 100}, {1, 1, 1, 1}}));
assertEquals(16, test.solution(new int[][] {{1, 2, 3, 4}, {5, 6, 7, 9}, {4, 3, 2, 1}}));
assertEquals(125, test.solution(new int[][] {{9, 5, 2, 3}, {9, 8, 6, 7}, {8, 9, 7, 1}, {100, 9, 8, 1}}));
assertEquals(20, test.solution(new int[][] {{4, 3, 2, 1}, {2, 2, 2, 1}, {6, 6, 6, 4}, {8, 7, 6, 5}}));