글 읽기 - 2565번 어디가 틀린지 모르겠습니다 ㅠㅜ

sangjin256 4년 전 1

감이 잘 안잡힙니다 도와주세요 ㅠㅜ

using System;
using System.IO;
using System.Collections.Generic;

public class Lecture 
{
	public static void Main(string[] args) {
		int n = int.Parse(Console.ReadLine());
		SortedDictionary<int, int> dic = new SortedDictionary<int, int>();
		int[] dp = new int[501];
		
		for(int i = 0; i < n; i++){
			int[] ab = new int[2];
			ab = Array.ConvertAll(Console.ReadLine().Split(' '), s => int.Parse(s));
			dic.Add(ab[0], ab[1]);
		}
		
		SortedDictionary<int, int>.KeyCollection keys = dic.Keys;
		
		for(int i = 0; i < 501; i++){
			dp[i] = 1;
		}
		
		foreach(var i in keys){
			foreach(var j in keys){
				if(j <= i){
					if(dic[i] > dic[j]){
						dp[i] = Math.Max(dp[i], dp[i-1] + 1);
					}
				}
			}
		}
		int mx = 0;
		for(int i = 0; i < 501; i++){
			mx = Math.Max(mx, dp[i]);
		}
		Console.WriteLine(mx);
	}
}

sangjin256 4년 전 1

생각해보다가 맞췄습니다!

그냥 최장 증가 부분 수열로 풀면되는데 괜히 어렵게 생각했네요 ㅎㅎ

using System;
using System.IO;
using System.Collections.Generic;

public class Lecture 
{
	public static void Main(string[] args) {
		int n = int.Parse(Console.ReadLine());
		SortedDictionary<int, int> dic = new SortedDictionary<int, int>();
		int[] dp = new int[501];
		
		for(int i = 0; i < n; i++){
			int[] ab = new int[2];
			ab = Array.ConvertAll(Console.ReadLine().Split(' '), s => int.Parse(s));
			dic.Add(ab[0], ab[1]);
		}
		
		SortedDictionary<int, int>.KeyCollection keys = dic.Keys;
		
		foreach(var c in keys){
			dp[c] = 1;
		}
		//전깃줄의 총 개수를 구하기 위해 사용
		int count = 0;
		
		foreach(var i in keys){
			count++;
			foreach(var j in keys){
				if(j < i){
					if(dic[i] > dic[j]){
						dp[i] = Math.Max(dp[i], dp[j] + 1);
					}
				}
			}
		}
		int mx = 0;
		for(int i = 0; i < 501; i++){
			mx = Math.Max(mx, dp[i]);
		}
		//전깃줄 개수에서 최장 증가 부분 수열을 빼면 없애야하는 전깃줄의 최소개수가 나온다.
		Console.WriteLine(count - mx);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2565번 어디가 틀린지 모르겠습니다 ㅠㅜ

sangjin256 4년 전 1

sangjin256 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말