[코딩테스트] Java 정수삼각형

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

삼각형 형태로 있는 숫자를 이차원 배열로 생각하여 문제를 풀었습니다. 현재 행의 i-1에 j열 또는 j-1의 합으로 문제를 풀었습니다.

여기에서 ArrayIndexOutOfBoundsException이 나오지 않게 체크를 해줍니다.

소스코드

int solution(int[][] triangle) {
        int len = triangle.length;
        int[][] ans = new int[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                ans[i][j] = triangle[i][j];
            }
        }

        // init
        for(int i = 1; i < len; i++) {
            ans[i][0] = ans[i - 1][0] + triangle[i][0];
            ans[i][i] = ans[i - 1][i - 1] + triangle[i][i];
        }

        for(int i = 2; i < len; i++) {
            for(int j = 1; j < i; j++) {
                ans[i][j] = Math.max(ans[i-1][j-1], ans[i-1][j]) + triangle[i][j];
            }
        }

        int answer = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++) {
            answer = Math.max(answer, ans[len-1][i]);
        }

        return answer;
    }
}

코드 설명

• 초기화
  
  • len: 삼각형의 높이.
  • ans: 각 위치까지의 최대 합을 저장하는 2차원 DP 배열.
  • 삼각형의 값을 그대로 ans 배열에 복사합니다.

for (int i = 1; i < len; i++) {
    ans[i][0] = ans[i - 1][0] + triangle[i][0]; // 삼각형 맨 왼쪽 경로
    ans[i][i] = ans[i - 1][i - 1] + triangle[i][i]; // 삼각형 맨 오른쪽 경로
}

삼각형의 왼쪽 끝 경로와 오른쪽 끝 경로는 고정된 값만 참조하므로 초기화합니다.

• 왼쪽 끝 경로는 위쪽 요소에서만 내려옵니다.
• 오른쪽 끝 경로도 마찬가지입니다.

for (int i = 2; i < len; i++) {
    for (int j = 1; j < i; j++) {
        ans[i][j] = Math.max(ans[i - 1][j - 1], ans[i - 1][j]) + triangle[i][j];
    }
}

• 중간 경로 계산
  
  • 위치 ans[i][j]는 위에서 내려올 수 있는 두 가지 경로 중 더 큰 값을 선택합니다:
    • ans[i-1][j-1]: 왼쪽 대각선 위에서 내려오는 경로.
    • ans[i-1][j]: 바로 위에서 내려오는 경로.
  • 이 중 더 큰 값을 선택해 현재 위치의 값을 갱신합니다.
• 마지막 행에서 가장 큰 값을 조회 후 반환합니다.