[백준] 11053 가장 긴 증가하는 부분 수열 - 실버 3

[오늘의 문제]

https://www.acmicpc.net/problem/11053

---

[오늘의 학습 키워드]

• DP, 브루트포스 탐색, 구현

---

1. 문제설명

 

수열이 주어질 때 해당 수열중에서 가장 긴 증가하는 부분 수열을 찾는 문제 입니다.

 

만약 1 2 1 2 3 이 주어진다면

 

이 수열의 길이는 3이 되겠죠

 

또 1 10 2 3 이 주어진다면

 

이 수열의 길이는 3이 됩니다.

 

이런식으로 주어진 수열 중에서 가장 긴 증가하는 부분을 찾는 문제 입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 256MB
• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

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

---

2. 접근방식

처음에는 문제의 예시만 보고 DP 테이블을 구성하기 위해 시간 복잡도 O(N)이 걸리는 코드를 구성해 보았습니다.

 

DP 테이블을 생성하고 초기화를 시켜준 뒤 현재 값을 기준으로 이전 값이 더 작은 수라면 현재 값을 +1 하는 방식으로 DP 테이블을 구성 하였는데 이렇게 하니 문제점이 1 2 1 2 3 같은 수가 주어졌을 때 문제 였습니다.

 

제가 비교하는 방식은 바로 이전 값 즉, 1 2 1 2 3 에서 1을 기준으로 비교하는 경우 이전 값이 2만 비교해서 수열의 길이가 달라졌습니다.

 

이 문제를 해결하기 위해서는 기준값을 설정한 뒤 기준값을 기준으로 이전 값들과 모두 비교하며 생성되는 부분 수열 중 가장 긴 값을 찾아주고 현재 값은 그 값보다 1 커져야 합니다.

 

쉽게말하면 여러 사람이 한줄로 줄을 서고 있을 때 나를 기준으로 내 뒤에 있는 사람들 중 나보다 키가 작은 사람들의 수를 찾아주고 내가 그 다음 수가 되는 것이죠

 

나보다 키가 작은 사람들의 수를 찾아주려면 기준 값을 기준으로 전체 탐색을 실시해 주어야 겠죠

이러면 2중 for 문을 이용해서 문제를 해결해 주어야 합니다.

 

기준값 i를 설정한 뒤 i 값보다 작은 값을 찾기 위한 비교값 j를 설정해 줍니다.

 

이 j는 i보다 앞에 있는 사람은 탐색하면 안되니 탐색의 기준이 i값 까지가 되겠죠

 

동작 순서를 생각해 보죠

 

1. 기준값 설정 -> 반복문 i

2. 수열의 길이를 저장할 임시 변수 필요 -> temp

3. 비교값 설정 -> 반복문 j

4. 비교값이 기준값보다 작은 경우 비교값이 가진 수열의 길이와 임시 변수가 가진 수열의 길이 중 더 큰값으로 바꿔주기

5. 비교값 이동

6. 3 ~ 4 반복

7. 기준값의 수열의 길이 설정 -> 임시변수보다 1 커야 함

 

이렇게 되겠죠 이를 코드로 구현해 보았습니다.

---

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
nums = [0] + list(map(int, input().split()))
DP = [0] * (N + 1)  # DP 테이블 생성 및 초기화

# 기준값
for i in range(1, N + 1):

    # 수열의 길이를 정하기 위한 임시변수
    temp = 0

    # 기준값을 기준으로 가장 큰 값 찾기
    for j in range(i):

        # 비교하는 값이 나보다 작다면 이 값과는 증가하는 수열이 된다.
        if nums[i] > nums[j]:

            # 현재 수열의 길이와 나보다 작은 값이 가진 수열의 길이 중 더 큰값을 찾아서 수열의 길이 바꿔주기
            temp = max(temp, DP[j])
    
    # 기준값은 그 길이보다 1이 더 커진다.
    DP[i] = temp + 1

# 이 값들 중 가장 큰 값 찾기
print(max(DP))

---

[코드설명]

입력을 받고 DP 테이블을 생성해 주는데 DP 테이블과 index를 맞추기 위해 입력받는 nums 에도 0을 추가하여 index를 맞춰 주었습니다.

 

1. 기준값을 설정해 줍니다

2. 현재까지 찾은 가장 긴 수열의 길이를 저장할 임시 변수 temp를 설정해 주었습니다.

 

이 값은 기준값이 바뀔때마다 초기화 되어야 하니 첫번째 반복문 아래에 설정해 주었습니다.

 

3. 비교값을 설정해 줍니다.

 

비교값은 i 보다 이전값들로 i를 넘어가면 안되니 비교 대상은 시작부터 i이전 까지가 되겠죠

 

4. 값을 비교해 줍니다.

 

증가하는 부분 수열을 찾아 주어야 하니 비교값은 기준값보다 작은 경우만 수열의 길이가 늘어나야 합니다.

 

이때 수열의 길이는 DP 테이블에 저장되어 있을 테니 DP 테이블과 temp 중 더 큰 값으로 수열의 길이를 바꿔줍니다.

 

모든 탐색이 종료되면 기준값의 수열의 길이를 입력해 주는데 당연히 1 커진값이 입력 되어야 하겠죠

 

모든 탐색이 완료되면 가장 긴 증가 하는 부분 수열을 가진 수를 DP 테이블에서 찾아 주어야 합니다.

 

마지막 index가 될 수도 있고 중간에 있을 수도 있고 처음이 가장 긴 증가하는 부분 수열일 수도 있죠

 

따라서 max를 이용해 값을 출력해 주었습니다

---

4. 결과

---

[회고]

처음에 쉽게 생각하고 문제를 접근했다가 틀려서 조금 고민했던 문제 입니다.

 

브루트포스 탐색을 이용해 전체를 탐색하기에는 N이 최대 1000이 주어져 시간 초과가 발생하지 않을까 생각했습니다.

 

그러나 다르게 생각해보면 최대 1000회 반복을 수행할 때 2중 반복문은 최대 999회 까지 반복을 실시하고 이 모든 동작과정을 계산하면 최대 500,500 회 반복이 수행되어 1초안에 해결이 가능하였습니다.

 

이생각을 한 뒤 전체 탐색으로 코드를 수정하였고

 

기준값과 비교값을 제대로 설정하여서 문제를 해결할 수 있었습니다.

 

기존과는 조금 다른 방식으로 DP 문제를 풀다보니 좀 더 헷갈렸던것 같습니다.