[백준][C#] 1912 연속합 - 실버2

문제 보기

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

1912번: 연속합

 

문제                           

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

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

 

 

입력                          

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

 

 

출력                          

첫째 줄에 답을 출력한다.

 

 

실버2 문제이며, 풀이 방법도 알고 보면 간단한데

개인적으로는 많이 헤맸다.

누적 합 -> 투 포인터로 접근했다가 잘 되지 않아서 보니까

다이나믹 프로그래밍으로 접근하는 문제였다...

 

어찌 됐든, dp로 접근하면 어렵지 않게 풀 수 있는 문제이다.

 

풀이방법                 

dp[n]은

0~n까지의 수 중에서,

n번째 수를 꼭 포함한다고 가정했을 때

구할 수 있는 제일 큰 연속 합으로 설정한다.

 

 

0~n까지 중에서 제일 큰 연속 합이라 생각하면 안 된다.

 

가장 큰 연속합은

max 변수를 하나 두고 dp[n]과 비교하며 갱신해 주는 방법을 사용했다.

 

 

풀이는 정말 간단하니 코드만 살펴보자.

// 크기 n의 int[] 배열을 만든다.
int[] dp = new int[n];
// 0번에서 0번까지, 0번이 들어가는 제일 큰 연속합은 당연히 0번 수와 동일하다.
dp[0] = nums[0];

// max 선언
int max = dp[0];
for(int i = 1; i < n; i++)
{
	// dp[i-1] + nums[i]와 nums[i] 중 더 큰 쪽을 dp[i]에 저장한다.
    dp[i] = Math.Max(nums[i] + dp[i - 1], nums[i]);

	// max값을 갱신해준다.
    max = Math.Max(max, dp[i]);
}

 

예제 2로 로직을 확인해보자.

// 2 1 -4 3 4 -4 6 5 -5 1

dp[0] = 2;
dp[1] = 3; // 2 + 1 > 1
dp[2] = -1; // 3 + (-4) > -4
dp[3] = 3; // -1 + 3 < 3
dp[4] = 7; // 3 + 4 > 3
dp[5] = 3; // 7 + (-4) > -4
dp[6] = 9; // 3 + 6 > 6
dp[7] = 14; // 9 + 5 > 5 // Max!!
dp[8] = 9; // 14 + (-5) > -5
dp[9] = 10; // 9 + 1 > 1

// dp[n-1]이 음수일 경우 걸러지는 것 확인.

 

 

이렇게 질문할 수 있다.

 

1. dp[i -1]에서 nums[i]를 더했는데 합이 더 작아지면 어떡해?

 

걱정할 필요 없다. dp[i-1]의 값은 max에 남아있을 것이니.

 

 

 

전체 코드

using System;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(reader.ReadLine());
            string[] inputs = reader.ReadLine().Split();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++)
            {
                nums[i] = int.Parse(inputs[i]);
            }

            int[] dp = new int[n];
            dp[0] = nums[0];

            int max = dp[0];
            for(int i = 1; i < n; i++)
            {
                dp[i] = Math.Max(nums[i] + dp[i - 1], nums[i]);

                max = Math.Max(max, dp[i]);
            }

            print.WriteLine(max);

            reader.Close();
            print.Close();
        }
    }
}