BAEKJOON / 백준 - JAVA 2847번 게임을 만든 동준이

2024.05.01기준 - 실버4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

게임의 각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 각 레벨의 점수를 조정하여 모든 레벨을 클리어할 때 얻는 총 점수를 최대화 합니다.

점수는 항상 양수이고 1만큼 감소시키는 것은 1번의 작업입니다.

 

저는 스택을 활용해 문제에 접근을 했습니다.

주어진 레벨의 점수를 스택에 저장한 후, 스택을 활용하여 각 레벨의 점수를 조정합니다.

레벨을 순서대로 스택에 넣으면서, 이전 레벨의 점수보다 현재 레벨의 점수가 더 높다면 점수를 조정합니다.

1. 스택에 레벨의 점수를 순서대로 넣습니다.
2. 스택에서 레벨의 점수를 하나씩 빼면서, 이전 레벨의 점수보다 현재 레벨의 점수가 더 높은지 확인합니다.
3. 만약 현재 레벨의 점수가 이전 레벨의 점수보다 낮다면, 현재 레벨의 점수를 감소시켜야 합니다. 이를 위해 점수를 감소시키는 횟수를 계산합니다.

 

 

코드

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t = Integer.parseInt(br.readLine());
		
		Stack<Integer> qu = new Stack<>();
		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			qu.add(n);
		}
		
		int now = qu.pop(), sub, count = 0;
		while (!qu.isEmpty()) {
			sub = qu.pop();
			
            // 현재 레벨의 점수가 다음 레벨의 점수보다 클 경우 현재 레벨의 점수를 갱신
			if (now > sub) {
				now = sub;
			} else { // 현재 레벨의 점수가 다음 레벨의 점수보다 작을 경우 점수를 조정하여 감소 횟수 계산
				count += sub - now + 1; // 점수를 조정하여 감소 횟수 계산
				now--; // 현재 레벨의 점수 갱신
			}
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
}