[JAVA][백준 7570][그리디] 줄 세우기 - 컴도리돌이

반응형

 

7570번: 줄 세우기

---

 

해당 문제는 놀랍게도 가장 긴 증가수열 알고리즘을 활용해서 풀어야 한다.

생각보다 어려워서 구글링 하여 다른 분들의 코드를 확인하여 해결할 수 있었다.

다른 분들의 코드가 현저히 짧은 것을 보고 

상심이 매우 컸다.

 

7570 문제는 줄의 맨 앞이나 맨 뒤로만 어린이들을 보내서 줄을 세워야 한다.

그렇기 때문에 연속된 수들 중 가장 긴 증가수열의 길이를 구하고

n에서 구한 길이를 빼면 최소 횟수를 구할 수 있다.

---

	package 그리디;
	import java.util.*;
	public class boj7076 {
	static Scanner sc = new Scanner(System.in);
	static int n;
	static int [] dp;
	static int solution(){
	n = sc.nextInt();
	dp = new int [n+1];
	for(int i=0; i < n ; i++){
	int tmp = sc.nextInt();
	dp[tmp] = dp[tmp-1] + 1;
	}
	Arrays.sort(dp);
	return n-dp[n];
	}
	public static void main(String[] args) throws Exception {
	System.out.print(solution());
	}
	}

view raw boj7570.java hosted with ❤ by GitHub