풀이

• 배열 하나를 두 그룹으로 나눠서, 두 그룹간의 합의차이가 최소가 되는 지점을 구합니다.
• 시각화하면 아래와 같습니다.

배열 a
a[1] a[2] a[3] a[4] a[5] >> 를 두 그룹으로 나눕니다


a[1]   vs   a[2] a[3] a[4] a[5]
a[1] a[2]   vs   a[3] a[4] a[5]
a[1] a[2] a[3]    vs  a[4] a[5]
a[1] a[2] a[3] a[4]    vs  a[5]

• 위 경우 반복적으로 배열의 합을 반복문을 돌아 구하게 되는데, 이러면 시간이 오래걸려 타임아웃이 납니다.
• 왼쪽 그룹과 오른쪽 그룹의 합을 구하고, 그 차이를 구하는데 원소가 많아지만 이에 비례해서 연산량이 많아지므로 이럴때 해결하는 기법이 DP 입니다.
  • 아래 코드처럼 누적합을 구하는 dp배열을 따로 만들어준다음에

  for(int i=1 ; i<len ; i++) {
    dp[i] = dp[i-1] + A[i];
  }

  • 좌 그룹의 합과 우 그룹의 합은 아래처럼 한방에 계산해 줍니다.

  int left = dp[i-1];
  int right = dp[len-1]-dp[i-1];

  • 위 방법처럼 누적합을 미리 구해놓으면 매번 배열의 구간합 계산을 일일이 해주지 않아 배열의 원소가 커도 시간초과가 나지 않습니다.
• 코테는 암기과목인거같아요,,....ㅋ...

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int[] dp = new int[A.length+3];

        final int len = A.length;
        dp[0] = A[0];

        for(int i=1 ; i<len ; i++) {
            dp[i] = dp[i-1] + A[i];
        }

        int mini = Integer.MAX_VALUE;
        for(int i=1; i<len ; i++) {
            int left = dp[i-1];
            int right = dp[len-1]-dp[i-1];
            int temp = Math.abs(left - right);
            mini = Math.min(temp,mini);

        }
        return mini;

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.solution(new int[] {3,1,2,4,3}));
    }
}

• 참고 : 효율성 통과 못하는 brute-force 버전의 코드

사라져따.. 나중에 찾아서 업로드 하겠습니다..