[백준 11568번] 민균이의 계략 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP를 이용하여 풀어보았습니다.

 

이 문제는 백준 11053번 가장 긴 증가하는 부분 수열과 문제는 동일 합니다.

 

그러나 일전의 문제의 경우 DP[N]을 구하기 위하여 1부터 N-1까지 반복하여 정답을 구하는 방식으로 구현하였습니다.

 

이 방법은 최종 길이인N을 구하기 위해서는 worst-case인 N * (N-1)번 반복을 수행하므로 시간 복잡도가 O(N²)이 됩니다.

 

만약 이번 문제 또한 일전의 방식으로 풀이 시 시간초과가 되게 됩니다. 하여 Lower Bound를 이용하여 시간복잡도가 O(nlogⁿ)인 알고리즘으로 풀이를 진행하였습니다.

 

예제 1번의 최초 값인 8의 경우 최초의 값이므로 List에 Add합니다.

8

 

2번째 값인 9의 경우 List에 담겨있는 값인 8보다 큰 값이므로 List에 Add합니다.

8

9

 

3번째 값인 1의 경우 Lower Bound를 이용하면 Index의 경우 0이 되게 됩니다.

하여 기존에 0번 Index에 있는 8과 교체 되게 됩니다.

1

9

 

4번째 값인 2의 경우 또한 Lower Bound를 이용하면 Index의 경우 1이 되게 됩니다.

하여 기존에 1번 Index에 있는 9와 교체 되게 됩니다.

1

2

 

마지막 5번째 값인 10의 경우 2보다 큰 값이므로 List에 Add하게 됩니다.

1

2

10

 

최종으로 만들어진 List의 길이는 바로 우리가 찾는 증가하는 부분 수열의 길이가 됩니다.

 

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stringTokenizer;

int num = Integer.parseInt(br.readLine());
List<Integer> dp = new ArrayList<>();
stringTokenizer = new StringTokenizer(br.readLine());

dp.add(Integer.parseInt(stringTokenizer.nextToken()));

for (int i = 1; i < num; i++) {
	int number = Integer.parseInt(stringTokenizer.nextToken());

    for(int j=0; j<dp.size(); j++){
        if(dp.get(j) >= number){
            dp.remove(j);
            dp.add(j, number);
            break;
        }

        if(j == dp.size()-1)
            dp.add(number);
    }
}

bw.write(dp.size() + "\n");
bw.flush();