[문제 링크]


최대 연속합을 구하는 문제이다. 숫자 배열과, 최대 연속합을 저장하는 배열이 따로 더 필요하다.


구하고자 하는 숫자 배열의 가장 끝부터 차례로 내려가며, 최대연속합을 찾고자하는 배열값과, 바로 뒤 배열을 기점으로 하는 최대 연속합과의 합을 비교하여 그 최대값이 최대 연속 합이다.


밑은 예제를 돌렸을 경우의 CACHE 배열의 값이다. 맨 마지막의 CACHE값은 자기 뒤의 값이 없으므로 -1이 된다. 그 다음부터 재귀를 탈출해나가며 최대연속합을 구해나간다.


 ARR

 10

 -4

 3

 1

 5

 6

 -35

 12

 21

 -1

 CACHE

 21

 11

 15

 12

 11

 6

 -2

 33

 21

 -1


예를 들면 ARR이 21인 값은, 자신의 값 21과, 바로 뒤를 기점으로하는 최대 연속합과의 합인 21-1=20을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다.

21인 경우에는 12와, 12+21=33 을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다. 


즉 이 문제의 점화식은 다음과 같다.


DP(i) = MAX(arr[i], arr[i] + DP(i+1))



위 로직에 전체의 최대연속합을 저장하는 변수를 따로 만들어 답을 구하였다. 밑은 이를 구현한 코드이다.


#include <cstdio> #include <algorithm> int n,arr[100001],cache[100001]; int dp(int num){ //기저 사례 : 마지막에 도달했을 때, 마지막 값을 시작으로 하는 최대 연속합은 자기 자신이므로. if(num==n){ cache[n] = arr[n]; return arr[n]; } int& ret = cache[num]; //뒤의 값을 기준으로 하는 최대 연속값을 구하는 재귀 실행. int mx = dp(num+1); //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는 최대 연속합과의 합중 최대값을 구한다. ret = std::max(arr[num],arr[num]+cache[num+1]); //지금까지 구한 연속합중 최대값을 구한다. mx = std::max(mx,ret); return mx; } int main(){ //초기화 scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&arr[i]); //구한 최대 연속합중 최대값을 찾는다. printf("%d",dp(1)); }


막상 풀고 보니 재귀로 푸는 것 보다 반복문이 훨씬 깔끔하게 나올 것 같았다. 밑은 재귀를 쓰지 않고 for문으로만 구한 코드이다.


#include <cstdio>
#include <algorithm>
int n,arr[100001],cache[100001];
int dp(){
    //가장 마지막 값은 그 자체가 최대연속합이므로 배열값을 넣어준다. 
    cache[n] = arr[n]; 
    int mx = arr[n];
    for(int i = n-1;i>0;i--){
        //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는  최대 연속값과의 합중 최대값을 구한다.
        cache[i] = std::max(arr[i],arr[i]+cache[i+1]);
        //지금까지 구한 연속합중 최대값을 구한다.
        mx = std::max(mx,cache[i]);
    } 
    return mx;
}
int main(){
    //초기화 
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    //구한 최대 연속합중 최대값을 찾는다. 
    printf("%d",dp());
}


'Algorithm > Problems' 카테고리의 다른 글

백준 - 9465 스티커  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15
백준 - 2294 동전 2  (0) 2016.03.07
백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28

+ Recent posts