[소프티어] 징검다리

문제 설명

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다.

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

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

 

https://softeer.ai/practice/6293

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

 

문제 풀이

사실 제가 문제를 제대로 이해하지 못한 것인지, test case는 통과하는데 반례가 있는지 정답이 아니라고 나옵니다.

문제의 조건에 대해서 좀 더 고민을 해봐야 할 것 같습니다...

import sys

N = int(input())
heights = list(map(int, sys.stdin.readline().split()))

cnt = 1
cur = 0
for i in range(1, N):
    if heights[cur] < heights[i]:
        cnt += 1
        cur = i
    #print(cnt, cur)
print(cnt)

 

 

정답 코드는 아래처럼 푸는 것입니다.

import sys
input = sys.stdin.readline

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

dp = [1] * N  # 각 돌까지의 최대 증가 부분 수열 길이
for i in range(1, N):
    for j in range(i):
        if heights[j] < heights[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))  # LIS의 길이 출력