[ 백준 / BOJ 2374 ] 같은 수로 만들기 ( JAVA / 자바 )

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

2374번: 같은 수로 만들기

 

문제

---

n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한번에 1씩 증가한다. A[1]과 A[n]은 인접해 있지 않다.

예를 들어 수가 {1, 1, 1, 1, 3, 3, 1} 이었다고 해 보자. Add(2)를 하면 A[2]의 좌우로 인접한 같은 수가 1씩 증가하니까 {2, 2, 2, 2, 3, 3, 1}이 된다. 여기서 Add(4)를 하면 {3, 3, 3, 3, 3, 3, 1}이 되고, 여기서 Add(1)을 하면 {4, 4, 4, 4, 4, 4, 1}이 된다.

이와 같이 Add라는 연산을 사용하여 A[1] = A[2] = A[3] = … = A[n]이 되도록 하려 한다. 이때, 최소 회수로 Add연산을 사용하는 방법을 찾는 것이 문제이다.

입력

---

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 차례로 A[1], A[2], …, A[n]이 주어진다. 모든 입력은 1,000,000,000을 넘지 않는다.

 

출력

---

첫째 줄에 최소의 Add연산 사용 회수를 출력한다. 이 값은 1025을 넘지 않는다.

풀이

---

stack을 이용하여서 풀면 간단!

모두 같은 값이 되게 하는 횟수는  가장 작은 값이 가장 큰 값이 되게 하면 구할 수 있다.

1️⃣ stack이 비었다면 push

2️⃣ 새로 입력된 값이 stack의 top보다

    👉 크면, 차이 만큼 답에 더해주고, pop 후 새로운 값을 push

    👉 작다면, pop 후 새로운 값을 push

    👉 입력되는 값 중, 가장 큰 값을 저장해준다.

3️⃣ 입력이 끝나면, stack의 모든 값을 pop해주면서 max 값과의 차이를 더해주면 끄읕🙋‍♀️

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main_BOJ_2374_같은수로만들기 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Long> stack = new Stack<>();

        int N = Integer.parseInt(br.readLine());
        long max = 0;
        long ans = 0;
        for(int i = 0 ; i < N ; i++){
            long x = Long.parseLong(br.readLine());
            max = Math.max(max, x);

            if(stack.isEmpty())
                stack.push(x);
            else{
                if(stack.peek() < x){
                    ans += x - stack.pop();
                    stack.push(x);
                }
                else if(stack.peek() > x){
                    stack.pop();
                    stack.add(x);
                }
            }
        }

        while(!stack.isEmpty()){
            long num = stack.pop();
            ans += max - num;
        }

        System.out.println(ans);
    }
}