6회차 - 알고리즘 기록 : 과유불급 (어려웠던거 다시!)

---

 

 - 여러개의 카드중에 L 부터 R 까지의 숫자를 더하고자한다.

 - L 부터 R 의 합을 한 수가 제일 큰 사람을 구한다.

 - 같은 숫자일 경우 먼저 구매한 사람을 구한다.

 

아래와 같은 나열된 카드가 있을 경우에

1번 카드	2번 카드	3번 카드	4번 카드	5번 카드
1	-1	5	2	3

 

예를들어보면 아래와 같다.

2번부터 4번의 합	6
1번부터 3번의 합	5

 

이렇게 계산하는 것을 부분합, 구간합이라고 한다.

선형공간에서 주어진 범위의 원소들에 대한 합을 계산하는 문제.

 

가장 쉬운 방법은 FOR 문을 이용해 L 부터 R 까지 더하는 것이지만 최악의 시간 복잡도를 가지고 있다.

고차원적이고 복잡한 정보는 단순한 여러 정보들의 조합으로 표현될 수 있다.

    -  고차원 적  정보 : 왼쪽 끝과 오른쪽 끝으로 표현된 범위 

    -  저차원 적 정보 : 오른쪽 끝으로만 표현된 범위 ( 왼쪽 끝은 항상 1 )

 

모든 범위를 0부터 ~ 범위까지 모두 가진 값을 가지고 있다면 ?

 

	1번 카드	2번 카드	3번 카드	4번 카드	5번 카드
cards	1	-1	5	2	3
더하기	[0] ~ [0]	[0] ~ [1]	[0] ~ [2]	[0] ~ [3]	[0] ~ [4]
rangeSum	1	0	5	7	10

 

rangeSum [R] 에서 rangeSum [L] 을 빼기한다면 L ~ R 의 구간합을 구할 수 있다.

 

public static Range getBestRange(int n, int m, int[] cards, Range[] ranges) {
    Range answer = ranges[0];
    long[] rangeSum = new long[n+1];
    rangeSum[0] = 0;
    

   // 누적합 배열

    for(int i=1;i<=n; i++){
        rangeSum[i] = rangeSum[i-1] + cards[i];
    }

    //구간합 큰 후보 선정
    for(Range r : ranges){
        r.totalPoint = rangeSum[r.right] - rangeSum[r.left-1];
        if(answer.totalPoint < r.totalPoint){
            answer = r;
        }
    }
    return answer;
}

---