티스토리 뷰

PS/백준

[백준/C++] 2104번 - 부분배열 고르기

unside 2021. 3. 19. 13:48

오늘의 문제!

https://www.acmicpc.net/problem/2104

입력

첫째 줄에 N이 주어짐

둘째 줄에 N개의 정수들이 주어짐

풀이

해당 문제는 분할정복으로 해결했고 3가지 경우로 나뉘어진다.

1번 mid를 기준으로 왼쪽의 배열에서 최대값이 나오는 경우
2번 mid를 기준으로 오른쪽 배열에서 최대값이 나오는 경우
3번 mid를 기준으로 왼쪽과 오른쪽이 겹쳐서 최대값이 나오는 경우
따라서 우선은 1번 2번은 mid기준으로 나누고 최대값을 구하면되니 먼저 구해준다

그다음 3번을 구하는데 mid를 기준으로 왼쪽과 오른쪽중 큰값을 우선적으로 선택해서 결과값을 구해보고 최대값이면 갱신을 해준다.
물론 이때 값이 최소 원소값보다 작으면 해당 값을 갱신해주고 해당 확인은 현재의 배열 전체를 확인식으로 진행한다.

소스

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
 
#include <stdio.h>
#include <iostream>
using namespace std;
 
long long A[100000];
 
long long func (int s, int e){
    if(s==e){
        return A[s]*A[s];
    }
    int mid = (s+e)/2;
    long long result = 0;
    result = max(func(s,mid),func(mid+1,e));
    long long V = A[mid], min = A[mid], l = mid, r = mid;
    while(l>s || r<e){
        long long p = l>s ? A[l-1] : -1; //왼쪽으로 갔을때 값
        long long q = r<e ? A[r+1] : -1; //오른쪽으로 갔을때 값
        if(p >= q){ //왼쪽으로 감
            V = V + p;
            if(min > p && p!= -1){
                min = p;
            }
            l--;
        }
        else{ //오른쪽으로 감
            V = V + q;
            if(min > q && q!= -1){
                min = q;
            }
            r++;
        }
        result = max(result,V*min);
    }
    return result;
}
 
int main(void){
    int N;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    cout << func(0,N-1);
    
    return 0;
}
 
 cs

생각정리

분할정복 문제를 많이 풀어보지 않았고 특히 재귀함수를 좋아하지 않았기에 제대로 배워야겠다.

지금은 기본적인 구조정도만 익숙해진것같다.

해당 문제를 풀때 여러 생각이 들었지만 대부분은 n제곱의 횟수를 넘어서 패스했다.

그래서 라이님의 https://blog.naver.com/kks227/220776241154 히스토그램 문제를 기반으로한 설명을 천천히 공부하고 소스를 이해하고 풀어보니 해결됐다.

저작자표시 비영리 동일조건 (새창열림)

'PS > 백준' 카테고리의 다른 글

[백준/C++] 1992번 - 쿼드트리  (0) 2021.03.23
[백준/C++] 1725번 - 히스토그램  (0) 2021.03.20
[백준/C++] 1629번 - 곱셈  (0) 2021.03.18
[백준/C++] 1493번 - 박스 채우기  (0) 2021.03.17
[백준/C++] 15748번 - Rest Stops  (0) 2021.03.12
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/09   »
일 월 화 수 목 금 토
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
글 보관함