[소프티어] 징검다리- python (레벨 3)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=390 

Softeer

풀이

문제를 보았을때 알수있는 힌트

시간 복잡도를 확인해보면 N이 N^2인 경우에도 10^8안에 있는 것을 알수있다.

부르트포스(완전 탐색) 문제로 풀면 쉽게 풀릴것이다.

또한 각 돌들을 이동 수를 가질수있게 dp를 활용한다.

입력 예제를 예시로 보자면

a의 리스트를 0부터 4까지 천천히 증가하며 비교하는데

a[0]은 3이므로 3에 갈수있는 곳은 1밖에 없다 이를 dp[0]에 넣어준다.

a[1]은 2이고 이보다 작았던 a값을 확인한다. 아쉽게도 작은 값은 없다.

a[2]은 1이고 이보다 작았던 a값을 확인한다. 아쉽게도 없다.

a[3]은 4이고 이보다 작았던 a값을 확인한다. a[0]~a[2]까지 모두 작다. 이중에서dp[0]~dp[2] 중에 큰 값만 이용한다. 모두 값이 1로 dp[3]은 1+1을 한 2가 된다.

a[4]는 5이고 이보다 작았던 a값을 확인한다. a[0]~a[3]까지 모두 작고 이중에서 dp가 큰것은 dp[3]=2이가 된다. 

이것에 +1을 한 dp[4]=2+1이 된다.

이때 dp의 최대 값을 출력하면 되는 문제이다.

import sys

input = sys.stdin.readline

n = int(input())

dp = [1 for _ in range(n)]

a = list(map(int,input().split()))

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

print(max(dp))

https://github.com/dydwkd486/coding_test/blob/main/softeer/징검다리.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리