연속합 | 백준 1912번

이번 문제는 시간 초과 때문에 생각을 많이 했다.
어쩌면 더 쉽게 풀 수 있는 걸, 전에 풀어봤던 다른 생각에 갇혀 있던 것 아니었나 싶다.
맨 처음 생각한 알고리즘은 다음과 같다.

#include <cstdio>//시간초과

int main() {
 int n, max=0, sum[100001];
 sum[0] = 0;
    
    scanf("%d", &n);
 
 for(int i=1; i<=n; i++)
 {
  scanf("%d", &sum[i]);
  sum[i] += sum[i-1];
        
        for(int j=0; j<i; j++)
  {
   max = max > sum[i] - sum[j] ? max : sum[i] - sum[j];
  }
 }

 printf("%d\n", max);
 
 return 0;
}

받으면서 다 더해서 순서대로 빼는 식으로 한건데... 시간 초과가 나더라
계속 줄일수 있는 방법을 고려했는데.. 생각보다 간단했다.

#include <cstdio>

int main()
{
 int n, max=-1001, sum[100001];
 sum[0] = 0;
    
    scanf("%d", &n);
 
 for(int i=1; i<=n; i++)
 {
  scanf("%d", &sum[i]);
        
        if(sum[i-1]>0)  sum[i] += sum[i-1];
        
        max = max > sum[i] ? max : sum[i];
 }

 printf("%d\n", max);
 return 0;
}

이거 생각하려고 그 시간을... 참.. 짜고 보면 간단하다.
max 값을 계속 받으면서, 합이 음수가 되면 버린다, 왜냐하면 음수 더하면 작아지니까 ㅋㅋ 전부다 음수만 있을 경우를 고려해서, 처음 max를 -1000보다 작은 값으로 잡았다.
if 문이랑 ? : 문이랑 같이 쓴거 보면.. 참 통일성 없다 싶다.

알고리즘 분류 : 다이나믹 프로그래밍

make better code

연속합 | 백준 1912번

Artikel Menarik Lainnya