백준 반도체 설계(Java 구현)

백준 문제를 풀어보기 시작한지 한달째. 아직도 나의 뇌에 있는 아이디어를 코드로 풀어내기가 어렵다.

물론 이 문제는 아이디어조차 떠오르지 않았기 때문에 조금 고민후 블로그들의 답변을 보았다. 

사람들의 글을 보니 처음으로 눈에 들어오는 단어가 있었다. 그것은 LIS(최장 증가 수열)이였다.

쉽게 말해 숫자들을 어떠한 수의 열들이 주어졌을 때, 그 숫자들 중에서 부분적으로 추출해 길이가 가장 긴 수열을 만드는 것이었다. 이를 구현하는 알고리즘은 꽤나 간단한 방법이였다.

 

1. arr배열과 dp배열 두가지를 선언한다.

2. dp배열의 첫번째 인덱스에 arr배열 첫번째 인덱스 값을 넣는다.

3. len이라는 인덱스의 갯수(dp배열의 길이)를 가변적으로 변화시킬 변수를 선언한다.

4. arr의 인덱스를 증가시키면서 arr배열의 값이 dp배열의 값보다 작을때 or 클 때를 분리해서 코드로 작성하면 된다.

 

아래 코드는 한 블로그에서 본따왔다. 지금은 모방이 최선이라고 생각하며 하고있다. 

 

public class Main{ 
  
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
 
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i =1; i<=n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());	
        }
        
        int[] dp = new int[n+1];
        dp[1] = arr[1];
        int len = 1;
        for(int i =2; i<=n ; i++) {
        	if(arr[i]>dp[len]) dp[++len] = arr[i];
        else {
        	int j;
        	for(j=1; j<=len;j++) {
        		if(arr[i]<=dp[j]) break;
        	}dp[j] = arr[i];
        }
		
        }
        System.out.println(len);
	}
}

 

위의 것을 해결하고 생기는 한가지 의문점이 들었다. 남는 숫자들은 1,3,5인데 이것들은 문제의 답인 2,3,5와 다르지않나? 다른 블로그들의 답에서는 무관하다고하는데 왜 무관한지 잘 모르겠다. 사실 LIS의 개념을 잘 모르는 걸지도 모른다. 그래도 LIS알고리즘을 통해 개념적으로는 문제가 원하는 바를 풀어 내었다고 생각하고 글을 마친다.