99클럽 코테 스터디 16일차 TIL : 그리디 알고리즘(백준 2847번)

 

 

 

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

 

 

 

---

 

 

🔎 문제 

스마트폰 게임
N레벨 -> 클리어하면 점수가 주어진다.
플레이어 점수: 점수의합 -> 순위 

쉬운 레벨이 어려운 레벨보다 점수를 많이받는 경우도 있는데
이를 해결하기 위해 특정 레벨의 점수를 감소시키려고 한다.
-> 각 레벨을 클리어 할때 주는 점수를 증가시키려고함

각 레벨 클리어하는 점수가 주어졌을때 몇번 감소시키면 되는지 구하세요

점수: 항상 양수, 항상 답이존재 , 정답이 여러가지면 최소한으로 하는 방법을 구하기
1만큼 감소시키는게 1번

입력: 레벨의 수 N(1<=N<=100)
각레벨을 클리어하면 얻는 점수가 첫번째 레벨~ 마지막레벨 순으로
점수는 20000보다 작은 양의 정수

 

 

💡 풀이

- 앞에서부터 순서대로 앞의 수보다 작으면, 앞의 수+1로 변경

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Ex2847 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int preScore = 0;
		int answer = 0;
		
		for(int i=0;i<n;i++) {
			int score = Integer.parseInt(br.readLine());
			
			if(i==0) {
				preScore = score;
				continue;
			}
			
			if(preScore>=score) {
				answer += preScore - score + 1;
				preScore = preScore + 1;
			} else {
				preScore = score;
			}
			
		}
		
		System.out.println(answer);
	}

}

 

=> 여러가지 경우의 수가 있고 가장 적게 변경한다는 조건을 잊고있었다.

 

그래서 뒤에서부터 시작하는 것으로 해결

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Ex2847_2 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		int preScore = 0;
		int answer = 0;
		
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		for(int i=n-1;i>-1;i--) {
			int score = arr[i];
			
			if(i==n-1) {
				preScore = score;
				continue;
			}
			
			if(preScore<=score) {
				answer += score - preScore + 1;
				preScore = preScore - 1;
			} else {
				preScore = score;
			}
			
		}
		
		System.out.println(answer);
	}

}

 

- 입력 값은 순서대로이기 때문에 배열에 저장했다.