백준 2812 크게 만들기

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

그리디!
흠.. 이걸풀면서 느낀거는 약간 어거지로 끼워맞춘 최적화 느낌이였다..

바로 본론으로

메인아이디어

1. 검사할 후보지를 설정
2. 검사후 최대값과 index 검출
3. 해당 index+1 부터 다시검사
4. index+1 부터 후보지 재설정 (2-3-4 반복)

해서 다뽑으면된다

이걸로 끝나면 좋겟지만 바로 Boom

why ?>

1. 9는 최대값이므로 9가나오면 바로 채택하고 넘어가는 Greedy
2. 남은 후보지와 골라야될 수가 같으면 그냥 통으로 선택해서 끝내는 Greedy가 필요

해당 방법으로 시간줄이니까 됨..

소스코드는 다음과같다..

import java.io.*;
import java.util.*;
public class 크게만들기 {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		String cur = br.readLine();
		
		
		int startindex = 0;
		int curnum = -1;
		int endindex = K+1; // 2번 
		int saveindex = -1;
		StringBuilder sb = new StringBuilder();
		loop:
		for(int i=0;i<N-K;i++) { // 개수고르기 N-K개까지
			
			for(int j=startindex;j<endindex;j++) {
				int cnum = cur.charAt(j)-'0';
				if(cnum==9) {
					curnum = cnum;
					saveindex=j;
					break;
				}
				if(cnum>curnum) {
					curnum = cnum;
					saveindex=j;
				}
			}
			sb.append(curnum);
			curnum =-1;
			startindex=saveindex+1;
			endindex++;
			
			int fullcount =  N-startindex; // 고를수있는풀
			int take = N-K - (i+1); // 총갯수중에 i개 골랏을때 그러면 남은 골를수는 TAKE
			
			if(take==fullcount) {
				for(int j=startindex;j<N;j++) {
					int cnum = cur.charAt(j)-'0';
					sb.append(cnum);
				}
				break loop;
			}
			
			
		}
		
		
		System.out.println(sb);
	}

}

그리디 유형은.. 많이연습해야할것같다..

일단 이제 DFS와 BFS로 넘어가보자 단골단골