[백준] 2374번 : 같은 수로 만들기 Gold4(골드4) - JAVA[자바]

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

문제 링크

성능 요약

메모리: 11832 KB, 시간: 72 ms

분류

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

제출 일자

2024년 6월 18일 21:43:46

문제 설명

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²⁵을 넘지 않는다.

접근 방법

1. 가장 작은 수가 가장 큰수로 되어야 한다.(최적의 방법)

2. 최근에 들어온 값과 동일한 값은 처리해주지 않는다.

3. 가장 작은수 보다  큰수가 온다면 가장 작은수를 뺀 값을 더해준 뒤 큰수로만 생각해주면 된다.(이미 큰 수로 값을 더해줬기 때문에)

4. 최근에 들어온 수보다 작은 수가 들어온다면 들어온 수를 제거한다.( 어차피 작은 수가 증가하면서 그 범위를 커버해준다.)

 

풀이 코드 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long answer = 0;
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            int value = Integer.parseInt(br.readLine());
            if(max < value) max = value;

            if (!stack.isEmpty()) {
                int top = stack.pop();
                if (top <= value) answer += value - top;
            }
            stack.push(value);
        }
        answer += max - stack.pop();
        System.out.println(answer);
    }
}