[백준] 11053번 파이썬

Heejun Kim·2022년 6월 12일
0

Coding Test

목록 보기
36/51

문제: https://www.acmicpc.net/problem/11053

문제 해결 과정

  1. 주어진 수열에서 연속해서 증가하는 숫자의 수열 중 가장 길이가 긴 수열을 찾는 문제다.

  2. 따라서 각 수열의 값을 탐색할 때, 현재 값을 기준으로 이전 값들을 탐색하면서 현재 값이 이전 값보다 클 때, 이전 값이 가지고 있는 수열의 길이를 +1하면서 가장 긴 순열을 찾으면 된다.

  3. 개인적으로 기존 수열을 그리고 그 밑에 가장 긴 수열을 구하는 과정을 직접 그려보면 이해가 훨씬 빠르게 될 것이라 생각한다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
dp = [1] * n
answer = 1

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

0개의 댓글