백준 11055 가장 큰 증가 부분 수열 (python)

문제

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

오답 정리

이 문제의 점화식과 규칙은 11053 문제의 유형과 너무 비슷했기 때문에 빠르게 찾을 수 있었다. 하지만 사소한 실수로 인해 시간을 너무 많이 뺏기고 문제를 풀지 못하는 불상사가 발생했습니다.

어디가 문제였는지 틀린 코드와 맞은 코드를 한눈에 비교하면서 분석해보도록 하겠습니다.

위 그림에서 차이점을 찾을 수 있나요? 저는 처음에 큰 문제가 없을 줄 알고 왼쪽처럼 코딩을 했습니다. 하지만 이렇게 코딩을 한 경우 예제는 커버가 되지만 모든 tast case를 만족 시킬수 없었습니다. 그럼 어디서 문제가 발생하였을까요?

다름 아니라 dp의 초기값에서 문제가 발생했습니다.

저는 DP문제를 풀 때 무의식적으로 dp = [0]x(n+1) 로 초기화를 합니다. DP에는 메모나 DP테이블로 사용하기 위해 당연히 내가 값을 저장하려고 선언하는 것이기 때문에 값은 0 아니면 NULL 같이 없어야 한다고 생각했습니다.

이 문제는 이러한 저의 부주의한 코딩하는 습관 때문에 거의 다 맞추고도 계속 틀리는 문제가 발생했습니다.

저는 고작 이런거 때문에 틀렸다는 것에 너무 억울해서 스스로 예시를 대입하며 문제를 찾아냈습니다.

만약 수열이 A = {100, 1, 2, 3} 이었다면 값은 어떻게 나와야 할까요?

바로 1, 2, 3이 증가하는 수열이고 정답은 6이 나와야합니다. 저는 제 코드에서 어떻게 잘못된 값이 나오는지 알아보기 위해 변수 i의 for문이 끝날때마다 값을 출력해봤습니다.

위 그림에서 처럼 값이 1이 덜 찍히면서 오답 5가 출력되었습니다.

저는 왜 제 코드에서 이런 문제가 발생하는지 알아보기 위해 직접 문제를 따져가며 풀어보았더니 그제서야 알 수 있었습니다.

if a[j] < a[i]:
    dp[i] = max(dp[i], dp[j] + a[i])

위 점화식에서 i=2일때,

dp[i] = a[i]이므로 a[i] 값을 dp[i]에서 처음부터 활용한다는 것을 확인할 수 있었습니다.

보기에서 보여준 예시는 처음부터 i= 2 일때 101이 나와 a[i]의 값을 무시해도 문제가 발견되지 않았습니다.

이러한 실수로 인해 (사실은 실력입니다..) 이번 문제에서 시간을 많이 뺏긴 것 같습니다.

다음부터는 점화식이나 규칙을 찾을 때 초기값이나 기저를 잘 확인하고 DP에서 무조건 0으로 초기화 하지 않고 꼼꼼히 생각해서 코드를 짜보기로 다짐했습니다.