[알고리즘] 백준 2847 게임을 만든 동준이 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 실버4
링크 : https://www.acmicpc.net/problem/2847

풀이

첫 줄은 총 입력의 갯수(n) 이다. > 예제에서 4개의 데이터
이후 n개의 줄에 실제 데이터가 입력된다.

즉, 이러한 데이터라고 볼 수 있겠다.
문제에서 '특정 레벨의 점수를 감소'라고 했다. 즉, 점수를 더하는 경우는 없다.
추가로, '점수를 내리는 것을 최소한으로 하는 방법'이라는 조건이 있다.
이를 통해 알 수 있는 점이 두 가지 있다.
1. n번째 레벨은 n+1번째 레벨보다 점수가 1만큼만 낮을 것
2. n+1번째 레벨은 n번째 레벨보다 점수가 1만큼만 높을 것
   (= n번째 레벨은 n-1번째 레벨보다 점수가 1만큼만 높을 것)
또한, 문제에는 '항상 답이 존재하는 경우만 주어진다.'라는 조건이 있다.
이게 무슨말일까?
위 그림을 살펴보자. 가장 높은 레벨인 7레벨의 점수는 2점이다. 그렇다면, 6레벨은 1점이면 된다. 그러나, 점수는 양의 정수라는 조건이 문제에 있으므로 5레벨 ~ 1레벨은 구할 수 없다. 이러한 경우가 없다는 말이다! 다시 문제로 돌아와보자.

레벨이 가장 높은 4레벨을 기준으로, 아래 레벨 (3 -> 1)이 현재 레벨보다 높을 경우, 현재 레벨보다 1만큼만 낮게 해주면 된다. 위와 같이, 동준이는 총 6번의 감소 연산을 수행하면 된다.! (예제 출력)

코드

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int ans = 0; // 정답, 동준이가 점수를 내린 횟수
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++)
			arr[i] = sc.nextInt(); // 입력을 받음
		for(int i = n-2; i >= 0; i--) {
			// n = 4일 경우, 배열의 index는 0, 1, 2, 3이 존재함.
			// 2번과 3번, 1번과 2번, 0번과 1번을 비교하고자 n-2부터 시작하여 0번까지 반복
			if(arr[i] >= arr[i+1]) { // 낮은 레벨의 점수가 높은 레벨보다 크거나 같은 경우
				int diff = arr[i] - arr[i+1] + 1; //n번째 수가 n+1보다 1만큼 작게 하기 위한 차이
				ans += diff;
				arr[i] -= diff;
			}
		}
		System.out.println(ans);
	}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.