[Beakjoon] #11055 - 가장 큰 증가 부분 수열

 

6번 정도 실패하고 반례 테스트케이스 보고 해결한 문제 ㅠ_ㅠ

 

처음 생각한 코드는 다음과 같다. 

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)

dp = [0] * (n + 1)
dp[1] = a[1]

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

# print(dp)
print(max(dp))

해당 코드로 문제에 주어진 입력 예제를 넣었을 때는 정답이 출력되지만 채점시 틀렸다고 떴다.

 

반례 
6
10 20 10 30 20 50

다음과 같이 입력이 주어졌을 때 내가 원했던 dp는 [10, 30, 10, 60, 30, 110]이다. 

하지만 처음 코드로 돌리면 [10, 30, 0, 60, 30, 110]이 나왔다.

 

반례를 찾고 고친 답안 

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)

dp = [0] * (n + 1)
dp[1] = a[1]

for i in range(1, n + 1):
    for j in range(1, i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], a[i] + dp[j])
        else:
            dp[i] = max(dp[i], a[i])

# print(dp)
print(max(dp))

 

a 배열의 세번째 값인 10을 기준으로 가장 큰 증가 부분 수열을 구할 때를 보자.

10보다 앞에 있는 수는 10보다 같거나 커서 for문의 if절에 걸리지 않는다. 

→ 결과적으로 해당 dp값은 초기화 상태 그대로 유지된다. 

 

따라서, 어떠한 값이 증가하는 수열의 첫번째 값이 되는 경우에는 초기화 값인 0이 아닌 해당 값을 할당해야 한다.

 

 

참고

https://thingjin.tistory.com/entry/%EB%B0%B1%EC%A4%80-11055%EB%B2%88-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC