DP -11053 , 11055 , 11722

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

11053번: 가장 긴 증가하는 부분 수열

11055번: 가장 큰 증가 부분 수열 (acmicpc.net)

11055번: 가장 큰 증가 부분 수열

11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net)

11722번: 가장 긴 감소하는 부분 수열

 

 

비슷한 맥락의 문제였기 때문에 한꺼번에 포스팅 하겠습니다. 

 

가장 긴 증가하는 부분 수열을 구하기 위해서는 해당 하는 위치에서 맨 처음값부터 하나씩 올라와 현재 위치하는 값보다 작은지 큰가를 하나하나 비교해나갔습니다. 그리고 만약 증가하는 모양새, 즉 이전 현재 값보다 이전에 작은 수가 있다면 수열 A와 크기가 똑같은 배열하나에 1을 더해주어서 값을 갱신해 주도록 하였습니다. 이때 수열 길이를 증가하는 배열은 무조건 1로 초기화해 주었습니다. 

 

수열 A의 처음부터 내려오면서 이전값보다 현재 값이 크다면 증가 부분 수열을 저장하는 배열에 1을 더해줍니다. 이때, 해당 숫자와 같은 인덱스의 증가 부분 수열의 값에다가 1을 더해주어야 연속되는 배열의 증가를 알아 낼 수 있습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());

        int number [] = new int[t];
        int dp[] = new int[t];

        int max = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }


        for(int i = 0; i<t; i++){
            dp[i] = 1;
            for(int j = 0; j<i; j++){
                if(number[i] > number[j] && dp[i] < dp[j]+1){
                    dp[i] = dp[j] + 1 ;
                }

            }
            
            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);

    }
}

11053코드

 

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());

        int number [] = new int[t];
        int dp[] = new int[t];

        int max = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }


        for(int i = 0; i<t; i++){
            dp[i] = number[i];
            for(int j = 0; j<i; j++){
                if(number[i] > number[j] && dp[i] < dp[j] + number[i]){
                    dp[i] = dp[j] + number[i] ;
                }
            }
            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);

    }
}

11055 문제 같은 경우에는 11053 문제의 코드와 같은 맥락입니다. 하짐나, 증가하는 수열의 길이의 최대가 아닌 값의 최대를 구해야 하기 때문에 길이를 1더해주는 대신 수의 값을 더해주어서 값중 최대값을 출력해주도록 변경하였습니다. 

 

package com.company;

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());

        int number [] = new int[t];
        int dp[] = new int[t];

        int max = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }


        for(int i = 0; i<t; i++){
            dp[i] = 1;
            for(int j = 0; j<i; j++){
                if(number[i] < number[j] && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1 ;
                }
            }
            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);

    }
}

11722 같은 경우는 이중 11053의 조건을 하나만 바꾸어주어서 해결 했습니다.