240302 [BOJ/백준] 2846. 오르막길

 

https://www.acmicpc.net/problem/2846

2846번: 오르막길

---

나의 코드

1. 강사님께서 알려주셨고 진우는 쉽게 풀었던 방법...ㅎㅎ

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

sum_v = 0
ans = 0
for i in range(N-1):
    if data[i] < data[i+1]:
        sum_v += (data[i+1]-data[i])

    else:
        if ans < sum_v:
            ans = sum_v
        sum_v = 0
if ans < sum_v:
    ans = sum_v

print(ans)

 

2. 아직은 해결하지 못한 나의 소중한 코드... 꼭 성공하겠다!

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


stack = []
i = 0

while i < N-1:
    if not stack:
        if arr[i] < arr[i+1]:
            stack.append(arr[i])
            i += 1
        else:
            i += 1
    else:
        x = stack.pop()
        y = arr[i]
        if x < y:
            stack.append(x)
            if y < arr[i+1]:
                i += 1
                if i == N-1:
                    stack.append(arr[i])

            else:
                stack.append(y)
                i += 1

        elif x == y:
            stack.append(x)
            if y == arr[i+1]:
                i += 1
            else:
                stack.append(y)
                i += 1

        else:  #x > y
            stack.append(x)
            if y < arr[i+1]:
                stack.append(y)
                i += 1
                if i == N-1:
                    stack.append(arr[i])
            else:
                i += 1


max_v = 0
for i in range(0, len(stack), 2):
    if max_v < (stack[i+1] - stack[i]):
        max_v = (stack[i+1] - stack[i])
# print(stack)
print(max_v)

결과

---

성공한 코드는 읽어보면 바로 이해되므로 설명은 패스!

밑에 실패한 것들은 모두 내가 도전했던 코드다. 진짜 1차원적인 방법으로 스택에 넣고 빼서 다음것과 비교하면서 모든 경우의 수를 구해 그에 맞는 숫자를 넣는 것이다. 오르막길의 최솟값과 최댓값만 stack에 남아있도록 짠 코드다.

주어진 입력에 맞는 출력이 나오는데 반례를 찾지 못해 강사님께 여쭤봤다. 11 / 12 20 1 3 4 4 4 4 4 11 1로 중간에 같은 높이가 여러 개일 때의 반례를 찾았고 해결했는데 또 틀렸다. 또 다른 반례 7 / 1 10 7 5 3 1 2로 내리막이 연속으로 될 때의 경우를 찾았고 그 문제도 해결했다. 그런데도 틀려서 포기했다. 일단 기초문제로 풀어보라고 하셨던 문제라 알고보면 쉬운 방식으로 풀어서 맞았다. 그치만 나의 코드도 월요일 시험이 끝나고 다시 도전해볼 것이다. 성공해서 스택으로 푼 미량이의 코드도 이해해보고 올려보겠다!!