11053_LIS

1. 문제

1) 문제

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

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

---

2) testCase

• input
  6
  10 20 10 30 20 50

• output
  4

• 출처
  백준

---

2. 문제 해설

1) 접근

• 여기는 저의 삽질구역입니다.. 해결방법으로 이동하세요
• 접근
  받아온 배열에서 i+1번째 항이 i항보다 클 경우 cnt++를 하였다.
• 실패요인
  최대 길이의 수열을 구해야하는데 이렇게하면 최대 수열의 길이 체크가 안된다.

2) 해결방법

① 코드

totalNum = int(input())
arr = list(map(int,input().split()))
dp = [0 for i in range(totalNum)]
for i in range(totalNum):
    for j in range(i):
        if arr[i] > arr[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))

② 해설

1. 입력 값을 받아온다.
2. 입력 arr의 크기만큼 dp list의 각 방에 0을 넣어준다. 여기서 dp는 수열의 길이를 나타내는 list입니다.
3. (★★★) 쉽게 j를 앞 번호 i를 뒷 번호라고 생각하면 된다. i가 하나씩 커질 떄 마다 자신보다 앞선 배열 중 값이 크고, 길이(dp)가 자신보다 클 때, 비교 상대를 가져와 자기자신의 수열의 길이에 넣고 1을 더한다.
   
     예를 들어
    i == 0일 때, j의 범위는 나타낼 수 없으므로 dp[0] = 1이 되고,
    i == 1일 때, j == 0 이 되고, arr[1] > arr[0] and dp[1] < dp[0] 이면, dp[1] = dp[0]을 넣는다.
    i == 2일 때, j == 0, 1이 되고, 순서대로 arr[2] > arr[0] and dp[2] < dp[0] 일 경우, dp[2] = dp[0]을 넣고,
    j == 1인 경우를 동일하게 실행하여, 최종적으로 1을 더한다. 이 후 i == 3일 경우부터는 전을 참조하면서 반복한다.
4. 이렇게해서 나온 dp의 최대 값을 나타내게되면, 최대 수열의 길이가 나타나게 된다.