소프티어 징검다리 Lv.3

현대 다니는 선배한테 조언을 얻어 소프티어에서 코딩테스트 공부를 한 지 3일차..

초반에는 어느 정도 풀렸으나 징검다리에서 막히고 말았다.

 

이번엔 내가 이해가 느려서 풀이를 보며 공부해도 오래 걸렸다.

그리하며 마지막쯤에 손코딩한걸 영상으로 찍어놨으니 그걸 보면 이해가 빠를 것이다.

---

문제 설명

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.

 

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다.

철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

 

돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

제약조건

1 ≤ N ≤ 3×103 인 정수

1 ≤ Ai ≤ 108 인 정수

입력 형식

첫 번째 줄에 돌의 개수 N이 주어진다.

두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

출력 형식

첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라.

---

1번째 제출 코드 [실패]

 

예제는 정답으로 나왔는데 실패가 떴다...

import sys
stone=[]
n=int(sys.stdin.readline())
step,h=1,0
result=0

stone=list(map(int,sys.stdin.readline().split()))
    
for i in range(n):
    step=1
    h=stone[i]
    for j in range(i,n-1):
        if stone[j+1]>h:
            h=stone[j+1]
            step+=1
    if result<step:
        result=step
             
print(result)

 

어째서인고하니.. 

이러한 경우에는 출력 4가 나오게 된다.

---

그리하여 어떻게 풀어야 하나 싶던 때, 좋은 영상을 알게 된다.

바로 알고 튜터..!

https://www.youtube.com/watch?v=CKJ7qpps4Qo&t=8s

 

이걸 보면서 힌트를 많이 얻었다.

이제는 코드를 짤 차례다.

---

최종 코드 [성공]

import sys

#n=돌 갯수
n=int(sys.stdin.readline())
#돌 갯수 사이즈, 크기가 1인 dp 만들어주기
dp=[1]*n

stone=[]
stone=list(map(int,sys.stdin.readline().split()))

for i in range(1,n):
    #이전에 걸은 돌 갯수 느낌나게 pre로 이름을 지었다
    pre=0
    for j in range(i):
        #만약 마지막 밟은 돌이 지금 검사하는 돌보다 높으면
        if stone[i] > stone[j]:
            #이전에 걸은 돌 갯수랑 지금 검사하는 돌의 dp값 중 최대를 pre에 넣어준다
            pre=max(pre,dp[j])
    dp[i]=pre+1

print(max(dp))

 

이건 나도 이해를 한 지 얼마 안 돼서 설명을 쉽게 하기가 아직은 어렵다.

그러므로 이해가 쉽게 손코딩으로 일일히 돌려본 영상을 첨부한다.

펜소리까지 녹음되어서 시끄러우니 꼭 음소거를 하자

https://www.youtube.com/watch?si=wMTtWaKelzITtFVW&v=SvbMWavID9Y&feature=youtu.be