[백준 - C#] 11053번 가장 긴 증가하는 부분 수열

문제링크

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

11053번: 가장 긴 증가하는 부분 수열

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

조건

시간제한 : 1초
메모리 제한 : 256 MB

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

문제정리

1. 수열 A가 주어질 때 가장 긴 부분 수열의 길이를 구해야합니다.
2. 수열은 앞에서부터 순차적으로 증가해야 합니다. ( 순서가 바뀔 수 없습니다. )
2. 수열 A의 크기는 ( 1<=N<=1000 )

이번 문제의 경우 A라는 수열이 주어질 때 가장 긴 부분 수열을 구해야 하는 문제입니다.

요즘 dp를 공부하고 있어 해당문제도 dp로 풀이를 진행하였습니다.

부분 수열이라 함은 선택된 수열보다 작은 수가 앞에오고 큰 수가 뒤에오게 됩니다.

그 말인 즉슨 선택된 수열 보다 작은 값들의 갯수가 길이가 되게 되는데 여기서 주의 할점으로는 작은 값들의 순서가 순차적으로 와야 한다는 것입니다.  ( 순서가 바뀌면 안된다 )

예를들어 ( 10 20 15 30 ) 의 경우 10 20 30으로 가야지 10 15 20 30 으로 세 번째 값이 두 번째로 갈 수 없다는 것입니다.

 

그렇게 풀이를 해보면

dp[N]까지 모든 값을 1로 초기화 하고

i번째 선택된 수열과 0부터 i-1번째 까지의 입력받은 수열 값을 비교하여 작은 값을 찾고

i번째 dp 값과 0부터 i-1 번째 까지의 dp 값을 비교하여 dp가 더 크다면 현재 dp 값을 갱신하는 식으로 길이를 구해내면 dp 안에 각 수열마다 길이가 저장되게 됩니다.

 

즉 0부터 i-1번째 원소가 i번째보다 작으면서 i번째 dp가 0부터 i -1번째 dp+1 값보다 작은 경우 입니다.

 

위의 말대로 풀이를 진행하면 아래와 같이 dp 안에 길이가 저장됩니다.

// dp[0] = 1 (10)
// dp[1] = 2 (10,20)
// dp[2] = 1 (10)    
// dp[3] = 3 (10,20,30)
// dp[4] = 2 (10,20) 
// dp[5] = 4 (10,20,30,50)

저장된 dp의 값을 모두 비교하여 최대값을 구하면 정답인 가장 긴 부분 수열의 길이를 구할 수 있습니다.

 

C# 코드

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
 
using static System.Console;
 
namespace BackjoonProject
{
    class Program
    {
        static void Main(string[] args)
        {
            // 11053
            StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
            StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
            int N = int.Parse(reader.ReadLine());
            int[] input = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
            int[] dp = new int[N];
 
            for (int i = 0; i < N; i++)
            {
                dp[i] = 1;
 
                for (int j = 0; j < i; j++)
                {
                    // 선택된 수열에 앞에 값보다 크고
                    // 저장된 수열의 갯수를 늘려주며 현재 선택된 수열의 길이를 변경
                    if (input[j] < input[i] && dp[i] < dp[j] + 1)
                        dp[i] = dp[j] + 1;                      
                }
            }
 
            // dp[0] = 1 (10)
            // dp[1] = 2 (10,20)
            // dp[2] = 1 (10)
            // dp[3] = 3 (10,20,30)
            // dp[4] = 2 (10,20)
            // dp[5] = 4 (10,20,30,50)
 
            int max = dp[0];
 
            // 가장 긴 수열의 길이를 찾아야 합니다.
            for (int i = 1; i < N; i++)
            {
                if (max < dp[i])
                    max = dp[i];
            }
 
            writer.WriteLine(max);
 
            writer.Close();
            reader.Close();
        }
    }
}
 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.