[2352번] 반도체 설계

문제 기출 : [https://www.acmicpc.net/problem/2352]

 

 

풀이 방법 #1

[backTracking] 접근   2일 동안 이 문제에만 몰두했다. 그냥 생각나는대로 경우의수를 나열하여 백트래킹 기법으로 하나하나 탐색하여 체크했다. 문제는 풀었지만 당연하게도 시간초과..(정답인지도 모르겠다.)   그래서 다른 방법을 채택했다.

문제 풀이 #2

public class Main {
	private static int maxCount = 0;
	public static void backTracking(int[] input, int start, int end) throws Exception {
		int count = 1;
		int temp = end;
		int flag = 0;
		
		if(start == input.length) {
			System.out.println(maxCount);
			return;
		}
		
		for (int i = start; i < input.length; i++) {
			System.out.println(start + " / " + end + " / " + input[i]);
			if(false == (input[i] < start || input[i] >= start && input[i] <= end) || (input[i] <= start && input[i] >= end)) {
				count++;
				
				if(input[i] > end) {
					end = input[i];
				}
			}
			
			if(i == input.length - 1) {
				i = start+flag;
				end = temp;
				flag++;
				
				if(maxCount < count) {
					maxCount = count;
				}
				count = 1;
			}
		}
		
		start++;
		backTracking(input, start, input[start-1]);
	}

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			long beforeTime = System.currentTimeMillis();
			int N = Integer.parseInt(br.readLine());
			int[] input = new int[N];
			int index = -1;
			
			
			StringTokenizer tokens = new StringTokenizer(br.readLine(), " ");

			while (tokens.hasMoreTokens()) {
				index++;
				input[index] = Integer.parseInt(tokens.nextToken());
			}
			
			backTracking(input, 1, input[0]);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}

 

 

풀이 방법 #2

[최장증가수열:LIS(Longest Increasing SubSequence)] 접근   선이 겹치지 않는 최대값을 구하기 위해서는 LIS를 사용해야한다. 즉, input을 받아 배열에 저장하고 해당 배열의 최장 증가 수열을 구하면 된다.   이 풀이 방법 역시 2일 정도 소요되었고 정말 나에겐 가장 어려운 문제가 아니었나 싶다.

 

문제 풀이 #2

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			int N = Integer.parseInt(br.readLine());
			int[] input = new int[N];
			int index = -1;
			
			StringTokenizer tokens = new StringTokenizer(br.readLine(), " ");

			while (tokens.hasMoreTokens()) {
				index++;
				input[index] = Integer.parseInt(tokens.nextToken());
			}
			
			int[] lisArray = new int[N];
			int lisSize = 1;
			lisArray[0] = input[0];
			
			for (int i = 1; i < N; i++) {
				if(lisArray[lisSize-1] < input[i]) {
					lisArray[lisSize] = input[i];
					
					lisSize++;
				} else {
					index = Arrays.binarySearch(lisArray, 0, lisSize, input[i]);
					index = index < 0 ? -index - 1 : index;
					lisArray[index] = input[i];
				}
			}
			
			System.out.println(lisSize);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}