[C#] 백준 11053번 문제풀이

문제번호: 11053

문제명: 가장 긴 증가하는 부분 수열

문제링크: https://www.acmicpc.net/problem/11053

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

안녕하세요. 다시 다이내믹 프로그래밍 문제로 돌아왔습니다. 이번 문제는 입력으로 주어진 수열에서 가장 긴 오름차순 증가수열 개수를 구하는 문제입니다. 

 

dp테이블을 N의 크기만큼 선언해주고 i, j반복문으로 mx값과 dp [j]의 크기를  비교하여 mx에 새롭게 갱신해 주고 mx = 1 값을 dp [i]에 저장한 후 i 반복문이 끝나면 dp테이블에서 가장 큰 값을 출력하게 하였습니다. 처음 풀이했을 때는 그리디 알고리즘 방식으로 풀이하였는데 반례 테스트 프로그램을 돌려보니 그리디 알고리즘의 한계를 발견하고 dp강좌영상을 시청하여 dp 알고리즘을 작성하였습니다.

 

다음은 정답코드입니다.

p.s 다이나믹프로그래밍은 정말 어려운 것 같습니다,, 앞으로 연습하는데 많은 시간을 들여야 할 것 같습니다 ㅠㅠ

public static void Main()
{
    StreamReader sr = new StreamReader(Console.OpenStandardInput());
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int N = int.Parse(sr.ReadLine());
    int[] A = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

    int[] dp = new int[N];

    for (int i = 0; i < N; i++)
    {
        int mx = 0;
        for (int j  = 0; j < i; j++)
        {
            if (A[i] > A[j])
            {
                mx = Math.Max(mx, dp[j]);
            }
        }

        dp[i] = mx + 1;
    }

    sw.WriteLine(dp.ToList().Max());

    sr.Close();
    sw.Close();
}