백준알고리즘 1912번 연속합 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 1912
• 문제명: 연속합
• 언어: C#
• 분류: 다이나믹 프로그래밍
• 비고: 

 

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

첫째 줄에 답을 출력한다.

 

풀이

기존까지 연속합의 최대값이 음수이면 더하지 않는다.

// 테스트 케이스의 수를 정수로 입력받아 저장
int testcase = Convert.ToInt32(Console.ReadLine());
// 정수들을 입력받아 배열에 저장
int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
// 연속합을 저장하는 배열 선언
int[] sums = new int[testcase];
// 연속합 배열의 0번째 항목에 입력한 0번째 숫자 대입
sums[0] = numbers[0];
// 가장 큰 연속합을 저장
int max = sums[0];

for (int i = 1; i < testcase; i++)
{
    // i - 1번째 배열을 끝으로 하는 연속값 최대값이 양수일 때
    if (sums[i - 1] > 0)
        // sums 배열의 i - 1번째 값과 입력한 i번째 정수의 합 대입
        sums[i] = sums[i - 1] + numbers[i];
    // i - 1번째 배열을 끝으로 하는 연속값 최대값이 양수가 아닐 때
    else
        // 0부터 i - 1번째를 제외하고 sums 배열에 삽입
        sums[i] = numbers[i];

    // 최대값 구하기
    if(max < sums[i])
        max = sums[i];
}
// 최대값 출력
Console.WriteLine(max);

 

후기

이것 또한 StreamReader와 StreamWriter 없이 해결되었다. 다만 제한시간 20분 내에 풀지 못했다. 심지어 for문을 2번 사용하는 것으로 해결해 보려고 했지만 시간 초과만 뜨고 말았다.

int testcase = Convert.ToInt32(Console.ReadLine());

int[] numbers = new int [testcase];

numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();

int max = 0;

for(int i = 1; i < numbers.Length; i++)
{
    for(int j = 0; j <= i - 1; j++)
    {
        if (max <= numbers[i] + numbers[j])
            max = numbers[i] + numbers[j];
        else
            max = Math.Max(numbers[0], numbers[i]);
    }
}

Console.WriteLine(max);

 

그래서 위에 시간 초과가 뜬 프로그램이 빅오 표기법으로 O(n^2)에 해당하다는 것은 알아냈다. 보통 프로그래밍할 때 빅오 표기법은 신경쓰지 않았는데 이 포스팅 이후부터 빅오 표기법을 문제 풀이에 적용해 보기로 결정했다. 새로운 문제를 풀거나 기존에 풀던 문제를 다시 풀 때 유용하리라고 본다.