(JAVA) 백준 2847번 : 게임을 만든 동준이

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

2847번: 게임을 만든 동준이

 

안녕하세요.

 

이 문제는 그리디 알고리즘 문제다.

 

난이도는 쉬운 편이기 때문에 핵심만 알면 된다.

 

 

즉, 이 문제의 조건만 기억하면 된다!

 

"낮은 레벨의 점수는 반드시 다음 레벨의 점수보다 낮아야 한다."

"점수 1을 낮추는 방법을 1이라고 했을 때, 최소의 방법을 구하라."

 

최소의 방법은 바로 

 

바로 이전의 레벨의 점수가 다음 레벨의 점수보다 1 낮은 것.

 

 

굳이 다음 레벨의 점수보다 2, 3, 10, 100 낮출 이유가 없다.

 

무조건 1정도 낮아야 최소의 방법을 구할 수 있다.

 

 

Come on!!!

다 끝났다!

 

 

 

간단히 매커니즘을 설명해보겠다. (풀 때 적어놨어서..)

 

 

매커니즘

---

  1)  가장 높은 레벨 - 1부터 탐색 시작 ( n >= 2 일 경우에만. 레벨이 하나면 굳이 낮출 필요가 없으니까.)

       ->  즉, 전체 레벨 개수-2 부터 0까지 for문 탐색

 

  2)  1)에서 index를 i라고 할 때, i-1 의 값과 i의 값을 비교한다.

        ->  i - 1의 값 < i의 값 인 경우, 통과

        ->  i - 1의 값 >= i의 값 인 경우, 우선 i - 1의 값 - (i의 값 - 1) 을 count 한다.  다음, i - 1의 값을 i의 값 - 1 로 설정한다.

 

  3)  count 출력!

 

 

 

이상입니다.

 

감사합니다.

 

 

 

소스코드

---