[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연산 사용 회수를 출력한다. 이 값은 1025을 넘지 않는다.
접근 방법
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);
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 14391번 : 종이 조각 Gold3(골드3) - JAVA[자바] (0) | 2024.06.19 |
---|---|
[백준] 14284번 : 간선 이어가기2 Gold5(골드5) - JAVA[자바] (0) | 2024.06.18 |
[백준] 10282번 : 해킹 Gold4(골드4) - JAVA[자바] (1) | 2024.06.18 |
[백준] 1253번 : 좋다 Gold4(골드4) - JAVA[자바] (0) | 2024.06.18 |
[백준] 1092번 : 배 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |