백준 11053 가장 긴 증가하는 부분 수열 c++,Kotlin (dp)

문제 출처 : www.acmicpc.net/problem/11053

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

알고리즘 분류

 

• 다이나믹 프로그래밍

풀이

 수열 A = {10, 20, 10, 30, 20, 50} 가 주어졌을 때 가장 긴 길이의 증가수열을 구하는 dp 문제다.

위의 예에서 출력은 10 20 30 50으로 4다

 

arr[6] = {0, 10, 20, 10, 30, 20, 50} 이 있을 때,

dp[1] = arr[1] > arr[0]이기 때문에 dp[0]+1; (dp[0]==0)

dp[2] = arr[2] > arr[1]이기 때문에 dp[1]+1;

dp[3] = arr[3] < arr[2~1]이기 때문에, dp[0]+1;

dp[4] = arr[4] > arr[3~1]이기 때문에 dp[3~0]중 최댓값에 +1;

이 과정을 반복하고, dp중 가장 큰 값을 출력한다.

아래 코드에선 입력을 따로 받았지만, 입력 for문에서 계산해도 된다.

코드(c++)

#include<iostream>
#include<algorithm>
using namespace std;

int arr[1001];
int dp[1001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[1] = 1;
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j]) {
                if (dp[i] <= dp[j]) {
                    dp[i] = dp[j] + 1;

                    ans = max(ans, dp[i]);
                }

            }
        }
    }
    cout << ans;

    return 0;
}

코드(Kotlin)

import java.util.*
import kotlin.math.*
fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = Integer.parseInt(br.readLine())
    val arr = IntArray(n)
    val dp = IntArray(n)
    val tk = StringTokenizer(br.readLine())
    dp[0]=1
    arr[0] = Integer.parseInt(tk.nextToken())
    var answer=1
    for(i in 1 until n){
        arr[i] = Integer.parseInt(tk.nextToken())
        for(j in i-1 downTo 0){
            if(arr[i]>arr[j]){
                dp[i]= max(dp[i],dp[j]+1)
            }
        }
        if(dp[i]==0){
            dp[i]=1
        }
        answer = max(answer,dp[i])
    }
    write("$answer")
    close()
}