아직 계정이 없으신가요? 회원가입

Dev. Talk

징검다리1 반례, 로직 문의

회원사진prettyrain85
106 views2021-10-17 20:31


import sys
n = int(sys.stdin.readline())  # 5, int

list_stone = [] # 리스트(돌의 높이, N개)
list_stone = list(map(int, sys.stdin.readline().split()))
list_count = [] # 리스트(시작돌을 밟았을때)

for i in range(n):
    list_count.append(1) # 처음 밟는 돌은 항상존재하므로 1로 시작

# ============================================================

# a = 0
# b = 1
# c = 1

for i in range(n-1):  
    start = i               # 첫번째 돌을 밟는돌 지정
    step = i + 1          # 다음 밟을돌 지정

    for j in range(n - i - 1):
        now = list_stone[start]  # 시작점의 돌을 밟았을때 그 이후로 가능한 돌을 계산
        nex = list_stone[step]
    
        if now < nex:
            start = step
            step += 1
            list_count[i] += 1       # 밟기가 가능한 돌의 개수를 카운트
            continue
    
        elif now >= nex:    # 밟는게 불가능하면 다음돌이 가능한지 이동
            step += 1
            continue
    
print(max(list_count))  # 가장 많이 밟는돌을 출력

# ============================================================


질문이 두가지 있습니다.


1) 위 로직에 대한 반례 부탁드립니다.


2) 알골선생님의 풀이는 다음과 같습니다.

    마지막으로 n 번째 돌을 밟는가고 가정하고, n 번째 돌을 밟기위한 돌은 n(0) ~ n(n-1) 까지 계산 후 max 값 출력


    하지만 저는 저렇게 안하고 다음과 같이 로직을 짰는데요


    첫번째 밟는 돌은 n 이라 가정하고 n(n+1) ~ n(final) 까지 밟는게 가능한 돌을 계산 후 max 값 출력


    제가 생각하는 알고리즘이 알골선생님과 다르긴하지만 결국에는 같은내용 아닌가요??