[Algorithm Champions] Week 4, No.3

문제

풀이

• 인접하지 않은 숫자들을 더한 최대 값을 반환하는 문제이다.

• 점화식을 세워 dp로 문제를 풀었다.

• array의 맨 처음부터 끝까지 돌면서 확인한다.

  • 현재 인덱스까지의 숫자들을 비교하여 더할 수 있는 가장 큰 값을 새로운 배열에 넣는다.
  • 이렇게 넣은 값을 비교하면서 바로 직전 값이 큰지, 아니면 두개 전 값에 현재 값을 더한 것이 큰지 비교하여 큰 값을 새로운 배열의 현재 인덱스에 넣는다.
  • 새로운 배열의 맨 마지막 값을 반환하면 가장 큰 값이 나오게 된다.

• 예시)
  새로운 배열 b
  b[0] = 75 (본인 값이 제일 크므로 그대로.)
  b[1] = max(a[0], a[1]) = 105 (두 값 중 큰 값 하나만 고를 수 있음)
  b[2] = max(b[0] + a[2], b[1]) = 195 (바로 직전(b[1])이 큰지, 두개 전 값에 현재 값을 더한 것(b[0]+a[2])이 큰지 비교한 후 현재는 후자가 크므로 195를 값에 넣는다.)
  ...
  (위와 같음)

코드

package com.company.w4;

/*
date: 21.07.07  21:03 ~ 21:47

input: int array
output: int
constraints: input val - positive integer
  인접하지 않은 원소들을 더한 최대 값을 반환
edge cases:
  array is empty -> return 0
  array.length == 1 -> return array[0]

Brute force
data structure: array
algorithm: traversal

[75, 105, 120, 75, 90, 135]
for문 2번 돌기
sum1 = 75 + max(120,75) -> 120 + max(90, 135) -> 135 = 75 + 120 + 135 = 330
sum2 = 105 + max(75,90) -> 90
       105 + 75 + 135

맨 뒤 a[5] 선택될 경우 -> a[4]=90 x, max(120,75)
     a[4]           -> a[3]=75 x, max(105, 120)
 0 ~ 5
 // 본인 포함
 b[0] = 75
 b[1]= 105
 b[2]=b[0]+ a[2] = 195
 b[3]=b[1]+a[3] = 180
 b[4]=b[2]+a[4] = 285
 b[5]=b[3]+a[5] = 315

 // 본인 미포함
 b[0] = a[0] = 75
 b[1] = max(a[0],[a1]) = 105
 b[2] = max(b[0] + a[2], b[1]) = 195
 b[3] = max(b[1] + a[3], b[2]) = 105 + 75  < 195 = 195
 b[4] = max(b[2] + a[4], b[3]) = 195 + 90 > 195 = 285
 b[5] = max(b[3] + a[5], b[4]) = 195 + 135 > 285 = 330


 */

// time: O(N), space: O(N)
public class No3 {
    public static void main(String[] args) {
        int[] array = {75, 105, 120, 75, 90, 135};
        System.out.println(maxSubsetSum(array));
    }

    public static int maxSubsetSum(int[] array) {
        // base case
        if (array.length == 0) return 0;
        if (array.length == 1) return array[0];

        int[] maxArray = new int[array.length];

        maxArray[0] = array[0];
        maxArray[1] = Math.max(array[0], array[1]);

        for (int i = 2; i < maxArray.length; i++) {
            if (maxArray[i - 2] + array[i] > maxArray[i - 1]) {
                maxArray[i] = maxArray[i - 2] + array[i];
            } else {
                maxArray[i] = maxArray[i - 1];
            }
        }

        return maxArray[maxArray.length - 1];
    }
}