[백준 - Python] 2374 - 같은 수로 만들기

0.  문제 링크

 

 

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

2374번: 같은 수로 만들기

---

1.  풀이 방법

 

 

일단 같은 숫자면 같은 그룹이므로, 중복으로 넣어야 되나 싶었다.

그래서 일단 넣을때부터 같은 그룹이면 하나의 숫자만 넣었다.

예를 들어서, 1 1 1 3 1이 입력되면, 1 3 1만 stack에 들어갔다.

 

그 이후에는 어떻게 숫자를 더할 것인가가 문제인데, 나는 다른 방법을 썼다.

인덱스를 기준으로 1 ~ n - 1 사이에 있다면 양 옆의 숫자 중 작은 숫자에 맞춰서 더했다.

근데 양 옆의 숫자가 현재 인덱스 숫자보다 작다면 그냥 패스했다.

만약 인덱스가 0이라면 오른쪽 숫자와만 비교했고, 인덱스가 맨 끝이라면 왼쪽 숫자랑만 비교했다.

이때 더하고, 비교하는 과정에서 인덱스 조정이 중요한데, 해당 부분에서 i를 잘 조절하면 완벽하게 인덱스를 조절한다.

최종적으로 while loop는 stack의 길이가 2 이하가 될때까지 했다.

 

문제를 풀다보면 길이가 3일 때도 끝내도 되지 않나 싶은데, 이러면 안 되는 이유가 있다.

만약 5 4 3 2 1를 입력하고, 길이가 3이 된다면 아마 stack은 5 4 3과 같을 것이다.

근데 이대로 연산을 끝낸다면 중복으로 계산을 하는 부분이 생긴다.

그래서 일부로 길이를 2이하가 될 때, 반복문을 끝냈고, 최댓값에서 나머지 값을 빼는 방식으로 횟수를 계산했다.

 

그림으로 그리면 다음과 같다.

왼쪽, 오른쪽 각기 다른 테스트 케이스

뭐 아무튼 이런 방식으로 풀었다.

---

2.  코드

 

 

import sys
from collections import deque
input = sys.stdin.readline


def sol():
    cnt = 0
    i = 0
    while (n := len(stack)) > 2:
        # 길이가 2와 같거나 작으면 모든 연산이 끝남
        # 1은 당연히 안 되고, 3은 4 1 5 같은 경우에 5에 인덱스가 맞춰져 있으면 잘못된 값을 출력함
        if 0 < i < n - 1:
            m = min(stack[i - 1], stack[i + 1])     # 양 옆에서 작은 애를 고름
            if m >= stack[i]:       # 만약 중간에 값이 더 작다면
                cnt += m - stack[i]
                del stack[i]
                if m == stack[i - 1]:       # 만약 왼쪽 값에 맞춰진다면 i를 한 번 더 빼야함
                    i -= 1
                i -= 1
        elif i == 0:
            if stack[0] < stack[1]:     # 오른쪽 애랑 비교함
                cnt += stack[1] - stack.popleft()
                i -= 1
        elif i == n - 1:        # 왼쪽 애랑 비교함
            if stack[n - 1] < stack[n - 2]:
                cnt += stack[n - 2] - stack.pop()
                i -= 2
        i += 1

    m = max(stack)
    while stack:        # 스택에 남아있다면, 최댓값에서 다 빼면 됨
        cnt += m - stack.pop()

    return cnt


if __name__ == "__main__":
    n = int(input())
    stack = deque()
    stack.append(int(input()))
    for _ in range(n - 1):
        # 어차피 같은 숫자는 하나의 그룹이니까, 숫자 하나만 넣음
        if (temp := int(input())) != stack[-1]:
            stack.append(temp)

    print(sol())

---

3.  마무리

 

 

분할 정복이라는데, 약간 분할 정복 느낌이 나기는한다...

생각보다 코드가 복잡?하다고 생각을 했는데, python3 기준 3등해서 기분이 좋다...