Softeer Level 3 징검다리 Python

문제 링크

https://softeer.ai/practice/6293

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
input = sys.stdin.readline

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

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

for i in range(1,N):
    nowCnt = 0
    for j in range(i):
      tmpCnt = dp[j]
      if stones[j] < stones[i]:
          if tmpCnt > nowCnt:
            nowCnt = tmpCnt
    dp[i] = nowCnt + 1

print(max(dp))

풀이 방법

- 처음 풀었을 때는 문제를 제대로 이해하지 못했고 반례를 먼저 찾게 되었다.

5
3 10000 2 4 5

5
10000 3 4 10001 5

- 답은 둘 모두 3이다.

- dfs로 풀이를 시도하다가 이것은 dp라는 것을 깨닫고 메모이제이션을 활용해서 풀었다.

- 높이에따라서 현재보다 작은 높이의 돌을 찾고 개수를 dp에 저장하면 된다.

 

느낀 점

- 문제를 잘 읽을 것

- 반례를 찾는 것은 귀찮지만 꼭 해야 한다는 점

- dp, dfs, bfs, 그리디 등 어떤 형식으로 풀지 먼저 생각해야겠다.