[▲][Softeer][level3] 징검다리 - 파이썬(Python)

https://softeer.ai/practice/info.do?idx=1&eid=390&sw_prbl_sbms_sn=139216 

Softeer

 

 

문제

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

 

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

 

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

 

 

 

 

---

 

틀렸는데

애초에 문제부터 이해를 제대로 못한 케이스...

 

해설을 보면서 문제를 이해했다.

 

 

문제의 핵심 포인트는 어떤 돌 하나만 밟고도 건널 수 있다는 점이다!!!!!!

 

 

 

예제 케이스를 그림으로 그려서 확인을 하면

 

이해를 돕기 위해 굳이 말로 설명을 해보면,, 

 

1개의 돌만 (5번돌) 밟고서도 이동이 가능하고,

2개의돌만 ( 2번, 4번돌)  밟고서도 이동이 가능하고,

3개의돌 (1번, 4번 5번돌)을 밟아서 3번만에 이동할 수도 있다는 뜻이다.

 

단 조건은 서쪽에서 동쪽으로 가면서 돌을 추가적으로 밟으려면  무조건 더 높은 걸 밟아야 한다는 점

최대로 밟아서 지나가게 되는 케이스에서 돌의 개수를 출력하면 된다.

 

 

감사합니다 알고선생님...

https://softeer.ai/community/view.do?idx=30&cd=edu&pageNo=1 

Softeer

 

알고선생님께서 얘기해주신 해결방법을 바탕으로 코드를 짰다.

 

1) dp테이블을 만든다. 모든 데이터를 1로 초기화한다.

>> dp 테이블에 존재하는 데이터는 ,, 자기가 마지막으로 밟는 돌이라고 가정했을 때 몇개까지 밟고 넘어가는가? 를 의미한다.

>> 예를 들어 돌이 5개 있다는 가정하에 5개 각각의 돌만 밟고 끝나는 경우가 존재하므로, dp 테이블을 1로 초기화한것이다.

 

2) 자기보다 왼쪽에 있으면서, 낮은 돌이 있나 체크하고  해당 돌들 중 가장 높은 돌에 도달하는 방법 + 1 을 할당한다.

 

 

 

 

💻 정답코드

import sys
input = sys.stdin.readline

n = int(input())
stones = list(map(int,input().split()))

dp = [1] * n

result = 0

for i in range(1,n):
    find = 0
    for j in range(i):
        if stones[j]<stones[i]:
            find = max(find, dp[j]) 
    dp[i] = find + 1

print(max(dp))

 

 

 

휴 문제 이해도 잘 못하고....

이해하고 나서도 이걸 잘 풀었을까 싶다...

 

금요일 안으로 다시 풀어봐야겠다 ㅠㅠ