[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2847번, 게임을 만든 동준이

문제 링크

2847번: 게임을 만든 동준이

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 각 레벨은 높일수록 클리어 점수가 높아야 합니다.

2. 점수를 1씩 감소시킬 수 있습니다.

3. 조건에 만족되도록 감소시키는 최소 횟수를 결과로 출력합니다.

4. 항상 답이 존재하는 경우만 주어집니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 레벨 기준 내림차순으로 점수를 감소시키도록 탐색합니다.

 

3. 탐색이 끝난 뒤 감소를 진행한 횟수를 결과로 출력합니다. 

 

 

점수 감소.

 

점수를 감소시킬 때는 자신의 다음 레벨보다 클리어 점수가 클 때입니다.

 

예를 들어.

Level 2 : 15

Level 3 : 14

Level 2는 Level 3보다 클리어 점수가 작아야 하고 최소한의 감소가 진행되어야 하기 때문에

Level 2 = Level 3 - 1 = 13이 되어야 합니다.

score[i] = score[i+1] - 1

감소하는 횟수 : score[i] - (score[i+1] - 1)로 구하면 됩니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 3

Level 1 : 5

Level 2 : 5

Level 3 : 5

 

2. 레벨 기준 내림차순으로 점수를 감소시키도록 탐색합니다.

 

Level 2(5) < Level 3(5)  : X

Level 2 = Level 3 - 1 = 5 - 1 = 4

감소한 횟수 = Level 2 - (Level 3 - 1) = 5 - 4 = 1번

 

 

Level 1(5) < Level 2(4) X

Level 1 = Level 2 - 1 = 4 - 1 = 3

감소한 횟수 = Level 1 - (Level 2 - 1) = 5 - 3 = 2번

 

3. 탐색이 끝난 뒤 감소를 진행한 횟수를 결과로 출력합니다. 

감소한 횟수 : 1번(Level 2) + 2번(Level 1) = 3번

3번을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 레벨 기준 내림차순으로 자신의 다음 레벨보다 클리어 점수를 작도록 탐색합니다.
• 탐색이 종료한 뒤 감소한 횟수를 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int answer = 0;
        int[] num = new int[N];
        //입력값 저장
        for(int i=0;i<N;i++)
            num[i] = Integer.parseInt(br.readLine());
        //레벨 내림차순 다음 레벨과 비교 진행
        for(int i=N-2;i>=0;i--){
            if(num[i] >= num[i+1]){	//다음 레벨보다 클 때
                answer += num[i] - (num[i+1]-1);	//감소한 횟수 구하기
                num[i] = num[i+1] - 1;	//감소 진행
            }
        }
        bw.write(answer + "");	//감소한 횟수 BufferedWriter 저장
        bw.flush();
        bw.close();
        br.close();
    }
}