[BOJ] 2352 - 반도체 설계

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/2352

2352번: 반도체 설계

난이도: 골드 3

사용언어: JAVA

 

풀이

겹쳐지지 않는 최대의 경우의 수를 묻는 문제이기 때문에, i 번째까지의 포트들을 겹쳐지지 않게 연결하는 최대 개수는 i보다 낮은 번호의 포트들을 겹쳐지지 않게 연결하는 최대 개수에 자기 자신을 포함하여 +1을 해주는 것입니다. 하지만 아무리 최대 개수라도 자신과 겹쳐지는 경우는 배제를 해야 합니다. 

 

따라서 정리하자면 i 번째까지의 포트들을 겹쳐지지 않게 연결하는 최대 개수는 i와 겹치지 않는 0 ~ i-1 사이의 j들을 구하고, 이 j들 중 최댓값을 구하면 됩니다.  

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N = Integer.parseInt(br.readLine());
        int i, j;
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int[] arr = new int[N]; // 입력 값을 저장하는 배열
        int[] result = new int[N]; // 최대 값을 저장하는 배열
        for (i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        result[0] = 1; // 1번 포트만 연결하는 경우 당연히 1개만 연결이 될 수 있음
        for (i = 1; i < N; i++) { // i 번째 포트까지 연결하는 경우 
            for (j = i - 1; j >= 0; j--) { // 0 ~ i-1 중에서
                if (arr[j] < arr[i]) { // i 번째 포트의 라인과 겹치지 않는 경우 중에
                    result[i] = Math.max(result[j] + 1, result[i]); // 최댓값을 저장
                }
            }
            if (result[i] == 0) // 0 ~ i-1 까지의 포트들의 라인이 모두 i와 겹친다면
                result[i] = 1; // 자기 자신만 연결하는 방법만 존재
        }
 
       Arrays.sort(result); // 결과를 소팅해서
        bw.write(String.valueOf(result[N - 1])); // 최댓값 출력
        bw.flush();
    }
}