2352

백준 2352번

Link: 2352번: 반도체 설계

---

문제 설명

역시 DP문제.

아주 오랫만에 자바로 문제를 풀었다.

사실 C++로 풀긴 했는데, 누군가의 제보에 의하면 같은 알고리즘으로 풀었을때 C++로는 시간초과가 나고, 자바로는 제시간안에 풀린다는 말이 있어 자바로 바꿔서 풀었다.

가장 긴 증가수열의 길이를 구하면 풀리는 문제다.

내가 짠 알고리즘은 다음과 같다.

1) DP 배열을 0으로 초기화한다.

2) 입력을 받는다.

3) i번째 인덱스에 입력받은 값이 들어간다고 가정할 때, 0부터 i-1까지의 j에 대해 port[j]가 port[i]보다 작을 때의 모든 DP값들 중 최대값을 찾는다.

4) DP[i]는 3에서 구한 최대값 + 1 이다.

5) DP 배열의 최대값이 구하고자 하는 답이다.

위와 같은 알고리즘대로 풀어봤더니 자바로는 제시간에 풀렸다.

예전에 배우기로는 여기다 이진검색까지 추가하면 더 빠르게 풀린다는 것을 배웠는데, 아직 제대로 이해하지 못해서 할수 있는 최선으로 이 알고리즘대로 풀었다.

이진검색도 같이 사용해서 C++로도 풀어낼 수 있도록 공부해보고 다시한번 풀어봐야겠다.

---

시간 터지는 C++ 코드

//
// Created by Keith_Lee on 02/03/2019.
//

#include <iostream>
#include <strings.h>

using namespace std;

int N;
int DP[40001];
int port[40001];

int main(){
    cin >> N;

    port[0] = 0;
    DP[0] = 0;

    for(int i=1; i<=N; i++){
        cin >> port[i];

        int max = 0;

        for(int j=0; j<i; j++){
            if(port[j] < port[i] && DP[j] > max){
                max = DP[j];
            }
        }

        DP[i] += max + 1;
    }

    int result = 0;
    for(int i=1; i<=N; i++){
        result = result < DP[i] ? DP[i] : result;
    }

    for(int i=0; i<=N; i++){
        cout << DP[i] << ' ';
    }
    cout << '\n';

    cout << result << '\n';

    return 0;
}

자바로는 돌아가는 정답 코드

//
// Created by Keith_Lee on 02/03/2019.
//

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2352 {

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

        int N = Integer.parseInt(br.readLine());

        StringTokenizer temp = new StringTokenizer(br.readLine());

        int[] port = new int[40001];
        int[] DP = new int[40001];

        for(int i=1; i<=N; i++){
            port[i] = Integer.parseInt(temp.nextToken());

            int max = 0;

            for(int j=0; j<i; j++){
                if(port[j] < port[i] && DP[j] > max){
                    max = DP[j];
                }
            }

            DP[i] += max + 1;
        }

        int result = 0;
        for(int i=1; i<=N; i++){
            result = result < DP[i] ? DP[i] : result;
        }

//        for(int i=0; i<=N; i++){
//            System.out.print(DP[i] + " ");
//        }
//        System.out.println();

        System.out.println(result);
    }

}

---