[Java] 백준 2374번 : 같은 수로 만들기

1. 문제

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

2374번: 같은 수로 만들기

 

 

2. 풀이과정

문제 유형에 stack이 써있는 걸 보고 풀었다.

안 보고 풀었으면 생각해내기 어려웠을 것 같았다.

입력을 처음부터 끝까지 받으면서, 구간마다 최소값을 찾아서 큰 값에서 뺀 값을 결과에 더해주었다.

마지막에 최대값에서 stack의 top에 있는 값을 빼주는 이유는 값이 감소하면서 끝날 경우 앞서 나온 최댓값에서 빼주는 형식이다.

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long result = 0;
        Stack<Integer> stack = new Stack<>();
        stack.add(Integer.parseInt(br.readLine()));

        int max = stack.peek();
        for(int i=1; i<N; i++){
            int now = Integer.parseInt(br.readLine());
            max = Math.max(max, now);
            
            if(now < stack.peek()){
                stack.pop();
                stack.add(now);
            }
            else if(now > stack.peek()){
                result += now - stack.pop();
                stack.add(now);
            }
        }

        System.out.println(result + max - stack.peek());
    }
}

 

 

결과