백준 - 11722. 가장 긴 감소하는 부분 수열 (MJ)

📖#11722. 가장 긴 감소하는 부분 수열

백준 실버2

🔍Institution

이전에 #11053. 가장 긴 증가하는 부분 수열 과 유사한 문제이다. 따라서 #11053번 문제를 풀었다면 어느정도는 쉽게 풀 수 있을 것이다. (나처럼 바보 짓만 하지 않는다면!)

🔍Approach

#11053. 가장 긴 증가하는 부분 수열 에서 풀이과정을 정리해둔 것이 있으니 그거 참고하기!

1. dp[0]

| i | 0 | 1 | 2 | 3 | 4 | 5 | | — | — | — | — | — | — | — | | arr | 10 | 30 | 10 | 20 | 20 | 10 | | dp | 1 | 1 | 1 | 1 | 1 | 1 |

• 10보다 큰 수를 카운트 한다. 10보다 큰 값은 없기 때문에 자기 자신을 포함한 1, dp[0] = 1
• 감소하는 수열 = {10}

1. dp[1]

| i | 0 | 1 | 2 | 3 | 4 | 5 | | — | — | — | — | — | — | — | | arr | 10 | 30 | 10 | 20 | 20 | 10 | | dp | 1 | 1 | 1 | 1 | 1 | 1 |

• 30보다 큰 수를 카운트 한다.
• 1번째 인덱스보다 큰 요소는 없기 때문에 자기 자신을 포함한 1, dp[1] = 1
• 감소하는 수열 = {30}

1. dp[2]

| i | 0 | 1 | 2 | 3 | 4 | 5 | | — | — | — | — | — | — | — | | arr | 10 | 30 | 10 | 20 | 20 | 10 | | dp | 1 | 1 | 2 | 1 | 1 | 1 |

• 10보다 큰 수를 카운트 한다.
• 2번째 인덱스 값인 10보다 큰 수는 1번째에 있는 30이 있다. 따라서 자기 자신을 포함해 dp[2] = 2
• 감소하는 수열 = {30, 10}

1. dp[3]

| i | 0 | 1 | 2 | 3 | 4 | 5 | | — | — | — | — | — | — | — | | arr | 10 | 30 | 10 | 20 | 20 | 10 | | dp | 1 | 1 | 2 | 2 | 1 | 1 |

• 20보다 큰 수를 카운트 한다.
• 3번째 인덱스 값인 20보다 큰 수는 1번째에 있는 30이 있다. 따라서 자기 자신을 포함해 dp[3] = 2
• 감소하는 수열 = {20, 10}

1. dp[4]

| i | 0 | 1 | 2 | 3 | 4 | 5 | | — | — | — | — | — | — | — | | arr | 10 | 30 | 10 | 20 | 20 | 10 | | dp | 1 | 1 | 2 | 2 | 2 | 1 |

• 20보다 큰 수를 카운트 한다.
• 3번째 인덱스값과 마찬가지로, 2번째 인덱스 값인 20보다 큰 수는 1번째에 있는 30이 있다. 따라서 자기 자신을 포함해 dp[2] = 2
• 감소하는 수열 = {30, 10}

1. dp[5]

| i | 0 | 1 | 2 | 3 | 4 | 5 | | — | — | — | — | — | — | — | | arr | 10 | 30 | 10 | 20 | 20 | 10 | | dp | 1 | 1 | 2 | 2 | 2 | 3 |

• 마지막 인덱스 값인 10보다 큰 수는 1번째에 있는 30과 3,4번째에 있는 20이 있다. 따라서 자기 자신을 포함해 dp[5] = 3
• 감소하는 수열 = {30, 20, 10}

🚩My submission

위의 Institution을 토대로 아래와 같은 flow를 짤 수 있다. (이 문제는 #11053과 유사하기 때문에 #11053과 차이가 거의 없다) 조건이 dp[i]보다 dp[j]보다 ‘크다’가 아니라 ‘작다’면으로 수정하면 된다.

1. n과 n만큼의 arr를 입력받는다.
2. 이중for문을 통해서 arr[i] < arr[j]라면 dp[i]값을 증가시킨다.
   1. i값을 j는 0 ~ i-1까지 확인 후, 가장 큰 값을 dp[i]에 넣어주어야 한다. dp[i] = max(dp[i], dp[j]+1)
3. dp에서 가장 큰 값을 print한다.

n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n
for i in range(1,n):
    for j in range(i):
        if arr[i] < arr[j]:
            dp[i] = max(dp[j]+1, dp[i])

print(max(dp))

• dp에 저장해야 할 때 min()이 아니라 max()를 하는 이유는 가장 ‘긴’ 수열을 찾는 것이고, 수열을 dp에 저장하는 것이 아니라 수열의 길이를 저장하는 것이므로, max를 이용한다.

🤭TMI

• 마음 급한 거 티 내기..