백준 1989 부분배열 고르기 2

작성일 | In |

문제 링크

  • https://www.acmicpc.net/problem/1989

알고리즘

  • 자료 구조
  • 분할 정복
  • 스택
  • 세그먼트 트리
  • 누적 합

풀이

분할 정복 방법을 사용했다.

첫 번째 방법은 딕셔너리에 최대 점수와 인덱스를 저장하는 것이다. dct[최대점수] = [i, j] 형식으로 값들을 저장했다.

그런 다음에 dct의 키 값에서 가장 큰 값으로 최대 점수와 최대 점수를 얻을 수 있는 인덱스를 출력하려고 했지만 메모리 초과 판정을 받았다.

그래서 두 번째 시도에는 최대 점수와 그 때의 인덱스 정보를 갱신하는 방법을 썼다.

사실 이 문제를 제일 처음 풀 때 사용한 방법이었는데, left와 right를 의미하는 x, y 변수만 global 선언하고, 최대 점수를 저장하는 result 변수는 global화 하지 않았다.

result 변수를 global 선언하지 않았기에 틀렸었는데 나는 그걸 알지 못하고 defaultdict으로 값을 저장하는 방법을 시도한 것이다.

결국, 다시 처음의 방법으로 돌아와서 재도전 끝에 성공했다.


defaultdict으로 시도한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from collections import defaultdict

n = int(input())
seq = list(map(int, input().split()))

dct = defaultdict(list)

def sol(start, end):
    
    if start == end:
        dct[seq[start] * seq[start]] = [start, start]
        return
        
    
    mid = (start + end) // 2
    
    l_sum = sol(start, mid)
    r_sum = sol(mid+1, end)
       
    left = mid
    right = mid + 1
    
    hab = seq[left] + seq[right]
    mini = min(seq[left], seq[right])
    
    dct[hab * mini] = [left, right]
    
    while start < left or right < end:
        if right < end and (start == left or seq[left - 1] < seq[right + 1]):
            right += 1
            hab += seq[right]
            mini = min(mini, seq[right])
            
        else:
            left -= 1
            hab += seq[left]
            mini = min(mini, seq[left])
            
        dct[hab * mini] = [left, right]
   
        
    


sol(0, n-1)

answer = max(dct.keys())
print(answer)
print(dct[answer][0] + 1, dct[answer][1] + 1)


global 선언해서 최대 점수와 인덱스 값을 갱신하는 방법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

n = int(input())
seq = list(map(int, input().split()))

x = 0
y = 0
result = -1

def sol(start, end):
    global x, y, result
    
    if start == end:
        if seq[start] * seq[start] > result:
            result = seq[start] * seq[start]
            x = start
            y = start
        return result
    
    mid = (start + end) // 2
    
    l_sum = sol(start, mid)
    r_sum = sol(mid+1, end)
    
    if l_sum > result:
        result = l_sum
        x = start
        y = mid
    if r_sum > result:
        result = r_sum
        x = mid + 1
        y = end
    
    left = mid
    right = mid + 1
    
    hab = seq[left] + seq[right]
    mini = min(seq[left], seq[right])
    
    if result < hab * mini:
        x = left
        y = right
        result = hab * mini
    
    while start < left or right < end:
        if right < end and (start == left or seq[left - 1] < seq[right + 1]):
            right += 1
            hab += seq[right]
            mini = min(mini, seq[right])
            
        else:
            left -= 1
            hab += seq[left]
            mini = min(mini, seq[left])
            
        
        if result < hab * mini:
            x = left
            y = right
            result = hab * mini
            
    return result
            
sol(0, n-1)
print(result)
print(x+1, y+1)