[SWEA 코딩] 최장 증가 부분 수열 - PYTHON #3307

소스 코드

t = int(input())

for tc in range(1,1+t):
    n = int(input())
    board = list(map(int,input().split()))

    # dp
    ans = [0 for _ in range(n)]

    # 시작 위치
    idx = 0
    while n > idx:
        num = board[idx]
        ans[idx] += 1
        score = ans[idx]
        for q in range(idx+1,n):
            if num < board[q] and score > ans[q]:
                ans[q] += 1

        idx += 1

    print('#{} {}'.format(tc,max(ans)))

 

---

해결 방법

1. dp로 접근

 

2. tc의 2번째 예시

idx / 값	4	2	3	1	5	6
초기	0	0	0	0	0	0
0	1	0	0	0	1	1
1		1	1	0	1	1
2			2	0	2	2
3				1	2	2
4					3	3
5						4

 

ex) idx가 0인 경우(4), 본인 선택하기 때문에 ans[0] += 1, 2,3,1은 4보다 작으므로 선택 X(ans값 그대로), 5,6은 4보다 크기 때문에 선택 O(ans값 +1)

idx가 1인 경우에는 ans 값(1)이 ans[4],ans[5](1)와 같기 때문에 +1 하지 않음

idx가 2인 경우에는 ans 값(2)이 ans[4],ans[5](1)보다 크기 때문에 +1 함

(idx가 1인 경우에는 ans[4],ans[5]의 값은 4를 선택해서 얻은 값이므로 2를 선택할 수 없음,

idx가 2인 경우에는 ans[4],ans[5]의 값은 2를 선택해서 얻은 값이므로 3을 선택할 수 있음)

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.