풀이최적의 방법을 찾기 위해 각 레벨마다 바로 다음 레벨의 점수와 비교해 필요한 만큼만 감소시키는 방식으로 접근해야 한다. 주어진 점수의 마지막에서부터 시작하여, 각 레벨의 점수가 이전 레벨보다 작거나 같아야 한다는 조건을 만족하도록 점수를 줄여나가야 한다.만약 현재 레벨의 점수가 이전 레벨보다 크거나 같으면, 이전 레벨의 점수를 현재 레벨보다 작도록 감소시킨다.전체 감소 횟수를 최소화하기 위해 현재 레벨의 점수에서 1을 감소시킨다. 예를 들어, 예제 입력 1번은 3, 4, 5 형식으로 만들어야 한다.마지막 5(last)부터 반복문을 시작하고, 이전 점수(before)와 비교한다.last 가 before 보다 작거나 같다면, before 의 실제 점수 값(scores[i -1])에 last - 1 을 매..

풀이N개의 문자 중, 가장 왼쪽 문자를 기준으로 다음에 오는 문자들과 비교한다.사전 순으로 빠른 문자는 가장 왼쪽(First)에 배치하고, 반대라면 가장 오른쪽(Last)에 배치한다.  문제를 읽고 예제 출력을 봤을 때 조금 의아했다.분명 사전 순서로 배치되었을 텐데 어떻게 ASDFG, AAABCBC가 나오는 걸까. A S D F G 의 알파벳 카드가 주어졌을 때, A를 먼저 뽑고 다음으로 S, D... 순서로 뽑게 될 것이다.현재 소지 중인 가장 왼쪽에 있는 카드와 다음으로 뽑은 카드를 비교한다.D 카드를 뽑았을 때, 사전 순서대로라면 A 카드 오른쪽에 배치해야하지만 이미 S 카드가 배치된 상태이다. 여기서 그리디 알고리즘을 다시 살펴보면모든 경우에 최적해를 보장하지 않는다.한번 결정한 것은 번복하지 ..

풀이거스름돈 동전의  최소 개수를 계산하는 것에 있어서 가장 효율적인 방법은 5원부터 사용하는 것이다.5원으로 가능한 한 많이 나누고, 나머지 금액을 2원으로 맞춰야 한다. 구현 1 - 실패import java.io.*;public class Main { static final int[] COINS = {5, 2}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int count = 0; ..

풀이생성 마법은 고양이를 1마리씩 소환하고, 복제 마법은 현재 고양이 수 이하만큼 소환할 수 있다. 생성 마법이든 복제 마법이든 최소한의 행동으로 입력된 n마리의 고양이를 소환해야 한다. 두 가지 마법 중 가장 최적의 마법을 선택하고, 현재 고양이 수에서 해당 마법으로 추가한 고양이 수를 더한다.이 과정을 고양이 수가 n이 될 때까지 반복한다. 이때, 마법이 선택될 때마다 행동 횟수를 증가시킨다. 구현1 - 실패(시간초과)import java.util.Scanner;public class Main { static long catCount = 0; // 현재 고양이 수 static final int GENERATE_COUNT = 1; // 생성 마법은 무조건 1마리씩 추가한다. public..