[BOJ] 가장 긴 증가하는 부분 수열 ★

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

 

1. 문제 이해 및 해결과정

 

테스트 케이스가 8 다음줄은 5 3 7 8 6 2 9 4 일 때 

2. 풀이방법

 1. LIS

#가장 긴 증가하는 부분 수열
#https://www.acmicpc.net/problem/11053
import sys
sys.stdin = open("input.txt","r")
n=int(input())
arr=list(map(int,input().split()))
arr.insert(0,0)
dp=[0]*(n+1)
dp[1]=1
res=1
for i in range(2,n+1): # 1다음수부터 찾으려는 값까지
    max=0
    for j in range(i-1,0,-1): #내 앞의 수 까지 최대값 찾기
        if arr[i]>arr[j] and dp[j]>max:
            max=dp[j]
    dp[i]=max+1
    if dp[i]>res:
        res=dp[i]
print(res)

 

3. 오답원인

 1. 반례 1   결과 1

: 아래 코드는 1을 입력했을 때 결과 0을 출력한다. 한 개 수를 입력하더라도 최소 한개의 길이는 나오므로 res=1로 해야한다. 

#가장 긴 증가하는 부분 수열
#https://www.acmicpc.net/problem/11053
import sys
sys.stdin = open("input.txt","r")
n=int(input())
arr=list(map(int,input().split()))
arr.insert(0,0)
dp=[0]*(n+1)
dp[1]=1
res=0
for i in range(2,n+1): # 1다음수부터 찾으려는 값까지
    max=0
    for j in range(i-1,0,-1): #내 앞의 수 까지 최대값 찾기
        if arr[i]>arr[j] and dp[j]>max:
            max=dp[j]
    dp[i]=max+1
    if dp[i]>res:
        res=dp[i]
print(res)

 

4. 알게된 점

- 백준 99%에서 에러 나는 경우는 범위의 끝부분에서 나는 경우가 많다.