집중국의 수신 기능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다.이 문장이 도저히 이해가 안 돼서 다른 블로그의 그림을 보고 이해했다.모든 센서는 적어도 하나의 집중국과 연결되어야 한다.6개의 센서들은 2개의 집중국에 포함되어야 하고, 2개의 집중국 집합으로 나눠보면 위 그림과 같다.그림의 수신 가능 영역의 합은  2 + 0 + 1 + 2 = 5이다.1 ~ 6, 7 ~ 9 로도 집합을 묶을 수 있지만 최소 거리를 구해야 하기 때문에 그림처럼 묶었다.  그림을 보면 모든 센서가 각 집중국에 연결되어 있지만 단절되는 부분이 보인다.단절 부분의 양 옆 센서 거리는 3으로 가장 큰 값을 가지고 있다.뭔가 보일 듯 말 듯 한데 예제 입력 2번도 그려보자.센서 개수가 많아 묶을 수 있는 방법도 많다.0 +..

입력과 복사 중 하나를 선택하여 컴퓨터 입력 시간을 최소화해야 한다.처음 daldidalgo가 만들어지는 시간은 8초이다.daldi : 5번 입력dal : 입력된 daldi의 dal 복사go : 2번 입력이후 N만큼 daldidalgo가 반복되고 마지막에 daldidan 으로 마무리된다. 먼저 daldidan이 만들어지는 경우는 2개이고, 둘 다 2초가 소요된다. daldida 복사, n 입력daldidalgo ... daldida 복사, n 입력다음으로 N만큼 반복되는 daldidalgo를 살펴보자.n = 2(daldidalgo) (daldidalgo) (daldida)(n) => 8 + 1 + 2 = 11n = 3(daldidalgo) (daldidalgo) (daldidalgo daldida)(n..

풀이최적의 방법을 찾기 위해 각 레벨마다 바로 다음 레벨의 점수와 비교해 필요한 만큼만 감소시키는 방식으로 접근해야 한다. 주어진 점수의 마지막에서부터 시작하여, 각 레벨의 점수가 이전 레벨보다 작거나 같아야 한다는 조건을 만족하도록 점수를 줄여나가야 한다.만약 현재 레벨의 점수가 이전 레벨보다 크거나 같으면, 이전 레벨의 점수를 현재 레벨보다 작도록 감소시킨다.전체 감소 횟수를 최소화하기 위해 현재 레벨의 점수에서 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..