softeer / python 징검다리

문제

문제보기

풀이

첨엔 단순히 반복 + flag 만 이용해서 풀려했는데
테스트케이스를 몰라서 왜 틀리는지는 모르겠지만 틀림 ㅠㅠ

for i in range(1, N):
    steped = False
    for j in range(i):
        if list_rocks[i] > list_rocks[j]:
            steped = True
            break

    if steped:
        cnt_steped += 1

print(cnt_steped)

그래서 찾아보니까 계수정렬로 풀면 된다해서 계수정렬로 다시 풀었당..

코드

import sys

N = int(sys.stdin.readline().strip())
list_rocks = list(map(int, sys.stdin.readline().split(" ")))


steped_rocks = [1] * N

for i in range(1, N):
    cnt_steped_rocks = 0
    for j in range(i): # 돌(i)와 이전에 지나온 돌들(j)를 비교하고자 함
        # print(list_rocks[i], list_rocks[j])
        if list_rocks[i] > list_rocks[j]: # 지금 밟고 있는 돌이 이전의 돌들과 비교해서 큰 경우
            if steped_rocks[j] > cnt_steped_rocks: # 중복으로 count 하는것을 방지하기 위해 추가
                cnt_steped_rocks = steped_rocks[j] # 여태까지지 밟은 돌의 갯수
        print(i, j, steped_rocks)

    steped_rocks[i] += cnt_steped_rocks
    # print(steped_rocks)

print(max(steped_rocks))

테스트케이스 알려줄 사람 구함...