백준 11053 - 세상에서 제일 긴 증가하는 부분 수열

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

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

 

 

이 문제는 풀긴 했는데 시간초과가 나서 제대로 푼게 맞는지 모르겠다.

 

시간초과 코드)

n = int(input())
nums = list(map(int, input().split()))
dp = [[1]] * n
d = [1] * n
s = 0
flag = 0
for i in range(n-2, -1, -1):
    for j in range(i+1, n):
        if nums[i] < nums[j]:
            d[i] = d[j]+1
            dp[i].append(d[i])
        d[i] = max(dp[i])

print(max(dp[0]))

뒤에서부터 맨 앞까지 반복문을 돌고 해당 위치의 앞에서부터 끝까지 이중 반복문을 통해 더 큰 것이 있으며 1씩 증가시키고 리스트에 추가하도록 구현했는데, dp를 찍어보니까 내가 원하는 것처럼 들어가지는 않았지만, 값이 잘 나오긴 한다.  나중에 복습할 때 dp에 들어간 원소들이 왜 그렇게 들어가는지 확인해 볼 필요가 있다.

 

풀이 코드는 다른 분의 포스팅을 참고했다.

https://bitwise.tistory.com/215

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

여기에 그림으로 잘 설명되어 있으니 이해가 안가면 다시 보도록 하자.

 

 

풀이 코드)

n = int(input())
nums = list(map(int, input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

생각보다 매우 간단하다.

위 풀이 코드를 리뷰해보자

 

n을 입력받아 길이가 n만큼의 리스트를 생성하였다.

이 리스트 dp는 모든 원소가 1로 초기화되어 있으며, 각 원소는 해당 위치까지에 올 수 있는 가장 긴 증가하는 부분 수열의 길이이다.

각 위치에 숫자가 하나씩 있기 때문에 길이를 1로하여 초기화한 것이다.

 

즉, 다음과 같이 말할 수 있다.

dp[0] : 인덱스 0까지의 증가 부분 수열의 최대 길이

dp[1] : 인덱스 1까지의 증가 부분 수열의 최대 길이

dp[2] : 인덱스 2까지의 증가 부분 수열의 최대 길이

dp[3] : 인덱스 3까지의 증가 부분 수열의 최대 길이

...

dp[0] = 1로 초기화된 상태에서 dp[1]을 구해보자

dp[1]은 인덱스 1까지의 증가 부분 수열의 최대 길이이다.

1번째 숫자가 0번째 숫자보다 크다면 => 즉, 0번째 숫자가 1번째 숫자보다 작다면 길이가 1이 늘어난 2가 dp[1]에 저장될 것이다. 아니라면, 그냥 원래 값이 1을 그대로 가지고 있어야 한다.

 

예제처럼 10 20 10 30 20 50에서 dp[3]을 구해보자

dp[0] = 1

dp[1] = 2

dp[2] = 1

dp[3]을 구하기 위해서는 0~2 인덱스의 수들이 3번째 수보다 작은지 확인하여야 한다.

보면 0, 1, 2 번째 수가 모두 3번째 수인 30보다 작으므로 다 부분 증가 수열이 될 수 있다.

그 중에서도, 가장 긴 길이를 저장해야되므로 dp[0], dp[1], dp[2] 중에서 가장 긴 길이를 갖는 dp값에 자기 자신을 포함하여야 하므로 길이 1을 더하여 저장하면 된다.

dp[1] = 2이 가장 긴 증가 부분 수열의 길이를 갖고 있으므로 2에 1을 더한 3이 dp[3]이 된다.

 

이처럼, 키포인트는 i번째까지의 증가 부분 수열의 최대 길이를 구하기 위해서는 이중 반복문을 사용하여 0번째 수부터 i-1번째 수까지 탐색 후 가장 긴 길이만 가져와 +1해주면 된다는 것이다.

코드로 나타내면 다음과 같다.

for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j]+1)

dp[i]는 j가 반복문을 돌아가는 동안 i번째인 수가 더 크다는 조건을 만족할 경우 기존의 dp[i]와 dp[j]+1을 비교하여 더 큰 값으로 계속 업데이트 해줌으로써 모든 수를 탐색하여 max값만 가져올 수 있어진다.

 

이중 반복문을 사용하여 max값을 계속 업데이트 해주며 dp[i]에 저장하는 부분이 평소에 잘 구현하지 않았던 코딩 스타일이라 신기하면서도 깔끔해서 좋았다. 앞으로 나도 자주 써먹어야즹

if nums[i] > nums[j]:
    dp[i] = max(dp[i], dp[j]+1)