2022.02.09 [백준] C# 전깃줄

 

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

2565번: 전깃줄

---

풀이

최소한의 겹쳐진 전깃줄을 제거하여 전부 겹치지 않게 만들라고 하는 문제이다. 이 문제를 반대로 생각하면 겹치지 않은 전깃줄의 최장증가수열을 찾은 뒤 전체 전깃줄의 수에서 빼면 제거해야하는 최소한의 전깃줄의 갯수를 구할 수 있다.

주어진 배열을 arr배열에 담고 최장 증가수열의 길이를 담을 count배열을 만들어 전체에 1을 설정해준다.(자기 자신만 있어도 최장 증가수열은 1이기 때문) 그리고 이중for문을 돌려 arr[i]나arr[j]가 0이면 그곳에는 전깃줄이 연결되어있지 않기 때문에 continue해주고 arr[i]의 값이 arr[j]값보다 크면 겹치지않기 때문에 count[i]와 count[j] -1 과 비교하여 큰값을 count[i]에 대입했다. 그리고 max를 만들어 count[i]와 비교 후, 큰 값을 max에 대입, 출력했다.

using System;
using System.Text;
using System.IO;
using System.Collections.Generic;
 
class Program
{
    static int[] arr;
    static int[] count;
    
    static void Cal(int n)
    {
        for(int i = 1; i < 501; i++)
        {
            
            for(int j = 1; j < i; j++)
            {
                if (arr[i] == 0||arr[j]==0)
                {
                    continue;
                }
                if (arr[i] > arr[j])
                {
                    count[i] = Math.Max(count[i], count[j] + 1);
                }
            }
        }
    }
    
    
 
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));    
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        arr = new int[501];
        for(int i = 0; i < n; i++)
        {
            int[] num = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            arr[num[0]] = num[1];
        }
        count = new int[501];
        for(int i = 1; i < 501; i++)
        {
            count[i] = 1;
        }
        Cal(n);
        int max = 0;
        for(int i = 1; i < 501; i++)
        {
            max = Math.Max(count[i], max);
        }
        sw.WriteLine(n - max);
        sr.Close();
        sw.Close();
    }
}