[소프티어] 징검다리/Python - Lv.3

❓문제

https://softeer.ai/practice/6293

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

언어별 시간/메모리

언어	시간	메모리
JavaScript	2초	256MB
C	1초	256MB
C++	1초	256MB
Java	2초	256MB
Python	2초	256MB

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

제약조건

1 ≤ N ≤ 3×10³ 인 정수
1 ≤ Ai ≤ 10⁸ 인 정수

✍🏻풀이

DP문제 기본적으로 모든 돌은 1번 밟을 수 있으므로 1로 초기화한다.
높이가 각 3, 2, 1, 4, 5 를 가진 5개의 돌이 주어졌을 때,
(3, 4, 5), (2, 4, 5), (1, 4, 5)로 높이가 5인 돌에 도착했을 때 최대 3개의 돌을 밟을 수 있다.
이중문을 사용하여 0~1, 0~2, 0~3 이러한 식으로 하나씩 늘려가며 최대로 밟을 수 있는 돌의 개수를 확인한다.

💻코드

import sys

input = sys.stdin.readline

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

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

print(max(dp))

📍후기

이 문제를 풀기 전에 DP문제를 풀었더니 혹시 DP인가 생각해보고 그냥 막 풀었다.
그런데 이 때 바로 앞의 돌의 높이가 큰지만 확인하여 처음에 (3, 4, 5), (2, 4, 5), (1, 4, 5)로 건널 수 있는 경우를 생각만 하고 코드로는 구현하지 않았었다. 이를 깨닫고 이중문을 사용하였다.
제발 문제 풀 때 케이스를 잘 생각해서 풀자..