백준 - 11053. 가장 긴 증가하는 부분 수열(MJ)

📖#11053. 가장 긴 증가하는 부분 수열

백준 - 실버2

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

🔍Institution

1. dp[0]

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

• 10보다 작은 수를 카운트 한다. 0보다 작은 인덱스는 없기 때문에 dp[0] = 1

1. dp[1]

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

• 20보다 작은 수를 카운트 한다.
• 1번째 인덱스보다 작은 요소는 nums[0]과 자기 자신을 포함해 총 2
• 증가하는 수열 = {10,20}

1. dp[2]

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

• 10보다 작은 수를 카운트 한다.
• 작은 수가 없다. 따라서 dp[2]는 자기 자신을 포함한 1

1. dp[3]

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

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

1. dp[4]

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

• 20보다 작은 수를 카운트 한다.
• 4번째 인덱스보다 작은 값은 10이 있다. 따라서 자기 자신을 포함해 dp[4] = 2
• 증가하는 수열 = {10,20}

1. dp[5]

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

• 20보다 작은 수를 카운트 한다.
• 5번째 인덱스보다 작은 요소는 10, 20, 30. 자기 자신을 포함해 dp[5] = 4
• 증가하는 수열 = {10,20,30,50}

🔍Approach

수열을 다 저장할 수도 있겠지만 굳이 그럴 필요보다는 횟수를 저장하면 된다. 즉, dp에는 수열의 길이를 저장한다.

위의 Institution을 토대로 아래와 같은 flow를 세울 수 있다.

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한다.

🚩My submission

n = int(input())
arr = list(map(int, input().split()))
dp = [1 for _ in range(n)]

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

i = 0, [1, 1, 1, 1, 1, 1]
i = 1, [1, 2, 1, 1, 1, 1]
i = 2, [1, 2, 1, 1, 1, 1]
i = 3, [1, 2, 1, 3, 1, 1]
i = 4, [1, 2, 1, 3, 2, 1]
i = 5, [1, 2, 1, 3, 2, 4]

💡TIL

• 문제를 이해를 다른 방향으로 해서 계속 ‘틀렸습니다’를 받았다. 다음부터는 문제를 제대로 읽고 풀이에 들어가자! 문제를 읽고 짧게 핵심을 적어보자.
  • 처음에 실패했던 코드

    n = int(input())
    dp = [0] * (n+1)
      
    nums = [int(n) for n in input().split()]
    dp[1] = 1 
      
    for i in range(1, n):
          
        if nums[i] > nums[i-1]:
            dp[i+1] = dp[i] + 1
        else:
            dp[i+1] = dp[i]
      
        print(dp[i])
    print(dp[n])