본문 바로가기

Problem Solving1223

[백준] 1715 카드 정렬하기 - Greedy / Java • 문제 링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.PriorityQueue; public class Main { public static voi.. 2022. 12. 25.
[백준] 2785 체인 - Greedy / Java • 문제 링크 2785번: 체인 희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그 www.acmicpc.net • 풀이 과정 적은 개수의 고리를 가진 체인부터 먼저 사용해서 최소값을 구해야 하므로, 각각의 체인의 고리의 개수를 입력받아 배열에 저장 후 오름차순 정렬한다. 이 후 적은 개수의 고리를 가진 체인부터 각각 확인하여 현재까지 확인한 체인의 고리 중 일부분을 사용해 남은 체인을 연결할 수 있다면, (sum >= cnt) 즉 남은 체인의 수 - 1은 열고 닫아야 할 최소한의 고리 수와 같으므로 반복문을 탈출해 해당 값 cnt 를 정답으로써 출력한다. • 풀.. 2022. 12. 24.
[백준] 2885 초콜릿 식사 - Greedy / Java • 문제 링크 2885번: 초콜릿 식사 학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ... www.acmicpc.net • 풀이 과정 최소 필요한 정사각형의 개수 k보다 같거나 크며 가장 작은 2의 제곱수를 구하여 이를 초콜릿의 최소 크기로써 n에 대입한다. 이어서 초콜릿의 크기가 k보다 클 경우 반으로 쪼개어 cnt++를 수행하고, 초콜릿을 쪼갠 만큼 필요한 k값에서 제외해야 하므로 k -= n을 수행한다. k가 0과 같거나 작을 때까지 이러한 과정을 반복하여, 미리 구한 초콜릿의 최소 크기 n과 쪼갠 횟수 cnt를 정답으로써 출력한다. •.. 2022. 12. 23.
[백준] 2141 우체국 - Greedy / Java • 문제 링크 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net • 풀이 과정 각 마을의 위치 및 인구 수 정보를 입력받으며 total 에 각각의 인구 수를 누적하여 총 인구 수를 구하고, 마을의 정보를 저장한 배열을 위치를 기준으로 정렬한다. 각각의 마을의 인구 수를 sum 에 누적하여 해당 값이 총 인구 수의 절반과 같거나 큰 시점이 (sum >= (total + 1) / 2) 해당 위치 기준으로 양 옆의 인구 수가 가장 근접.. 2022. 12. 22.
[백준] 2212 센서 - Greedy / Java • 문제 링크 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net • 풀이 과정 예제 입력 1을 예시로 1, 3 구간과 6, 9 구간에 집중국을 2개 설치 시, 수신 가능영역의 최소 길이는 2 + 3 = 5 가 된다. 이는 각각의 수신 가능한 센서를 오름차순 정렬 및 센서 간의 거리를 구해 더한 값, 0 + 1 + 2+ 2 = 5 와 같고, 이를 일반화하여 알고리즘을 풀이한다. 센서의 좌표를 입력받아 오름차순 정렬 후, 각 센서 간 거리를 구해 dist 배열에 저장하고, (dist[i] .. 2022. 12. 21.
[백준] 2012 등수 매기기 - Greedy / Java • 문제 링크 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net • 풀이 과정 불만도의 합을 구하기 위해 학생이 예상한 등수와 실제 등수의 차를 구하되, 그 값이 최소가 되기 위해 오름차순으로 예상 등수를 정렬한 후에 값을 구한다. 이때 모든 학생이 자신의 등수를 1로 예상할 경우, 불만도의 합이 int 범위를 벗어날 수 있기 때문에 long 형으로 sum 변수를 선언한다. 이후 각각의 차를 구해 sum 변수에 누적한 값을 정답으로써 출력한다. • 풀이 코드 import java.io.BufferedReader; im.. 2022. 12. 20.

티스토리툴바