BOJ_2374_같은 수로 만들기 (Java)

[Gold IV] 같은 수로 만들기 - 2374

문제 링크

성능 요약

메모리: 14348 KB, 시간: 108 ms

분류

자료 구조, 그리디 알고리즘, 스택

제출 일자

2024년 12월 26일 18:19:39

문제 설명

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연산 사용 회수를 출력한다. 이 값은 10²⁵을 넘지 않는다.

문제 풀이

코드

package BOJ_2374_같은수로만들기;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2374_같은수로만들기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        long res = 0;
        int max = 0;
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (max < num) max = num;
            if (!stack.isEmpty()) {
                int p = stack.pop();
                if (p <= num) res += num - p;
            }
            stack.push(num);
        }

        // 마지막에 1 5 2 이렇게 끝나면 2의 경우 최댓값까지 올려주는 계산이 추가로 필요
        res += max - stack.pop();
        bw.write(String.valueOf(res));

        bw.flush();
        bw.close();
        br.close();
    }
}