분할정복
OJS 연습문제
D)
문제설명 : 실수 a와 정수 b가 주어졌을 때, a의 b제곱을 정확하게 계산하는 프로그램을 작성하시오.
입력 : 첫째 줄에 a와 b가 주어진다. (0 < a < 100, 1 ≤ b ≤ 100) a는 최대 소수점 9자리이며, 소수가 0으로 끝나는 경우는 없다. a는 항상 소수점이 포함되어 있다.
출력: 첫째 줄에 a의 b제곱을 출력한다.
입력 예시
3.141592 3
출력예시
31.006257328285746688
import java.util.Scanner;
import java.math.BigDecimal;
public class Main {
private static void solve() {
Scanner sc = new Scanner(System.in);
BigDecimal a = sc.nextBigDecimal();
int b = sc.nextInt();
System.out.println(pow(a,b).toPlainString());
}
private static BigDecimal pow(BigDecimal a, int b) {
if(b%2==0)
{
if(b==1) return a;
else if(b==0) return BigDecimal.ONE;
else return pow(a,b/2).multiply(pow(a,b/2));
}
else
return pow(a, b - 1).multiply (a);
}
public static void main(String[] args)
{
solve();
}
}
E)
문제설명 : 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.
입력 : 1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)
2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)
출력: 첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.
입력 예시
7 5
100
400
300
100
500
101
400
출력예시
500
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;
public class Main {
private static void solve() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
int left = a[0];
for(int i=0; i<a.length; i++) {
if (left > a[i]) left = a[i];
}
System.out.println(compare(left, sum, n, m, a));
}
private static int compare(int left, int right, int n, int m, int[] a) {
if (Math.abs(right-left) <=1) return left;
int point = (left + right) / 2;
int count = counting(point, a, n);
if (count <= m) return compare(left, point, n, m, a);
else return compare(point, right, n, m, a);
}
private static int sum(Stack<Integer> stack) {
if (stack.isEmpty()) return 0;
else {
int sum = 0;
for (Integer i : stack) {
sum += i;
}
return sum;
}
}
private static int counting(float point, int[] a, int n)
{
int count=1;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++)
{
if (point <= sum(stack) + a[i]) {
stack.clear();
count++;
stack.push(a[i]);
}
else stack.push(a[i]);
}
return count;
}
public static void main(String[] args)
{
solve();
}
}
C)
문제 설명 : 평면상에 n개의 점 (P1, …. , Pn) 이 놓여져있다고 했을 때, 거리가 최소인 두 개의 점을 구하고 그 거리를 알고 싶다.
입력 설명 : 입력은 첫 번째 줄에 정수로 된 점의 개수 n이 주어진다.
두 번째 줄부터 n+1번째 줄까지 2개의 정수 x,y가 공백을 사이에 두고 주어진다.
i+1번째 줄은 Pi 의 x,y 좌표를 의미하고 n개의 점에 대해서 주어지게 된다.
점의 개수는 2 ≦ n ≦ 500000 , 좌표의 범위는 -10000 ≦ x,y ≦10000로 주어진다.
또한, 모든 점의 좌표는 같은 것이 없이 다른 것으로 한다.
출력 설명 : 가장 가까운 두 점 사이의 거리의 제곱을 출력하시오.
입력 예시 :
3
5 5
0 0
-3 -4
출력 예시 :
25
import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static class XComp implements Comparator<Point> {
@Override
public int compare(Point o1, Point o2) {
return o1.x - o2.x;
}
}
public static class YComp implements Comparator<Point> {
@Override
public int compare(Point o1, Point o2) {
return o1.y - o2.y;
}
}
public static double divide(ArrayList<Point> locations) {
if(locations.size() == 1) return Double.MAX_VALUE;
// 정렬
locations.sort(new XComp());
// 왼쪽, 오른쪽 나누기
int nArray = locations.size() / 2;
ArrayList<Point> leftArray = new ArrayList<Point>(locations.subList(0, nArray));
ArrayList<Point> rightArray = new ArrayList<Point>(locations.subList(nArray, locations.size()));
divide(leftArray);
divide(rightArray);
// 최소값
double min = Math.min(calcMin(leftArray), calcMin(rightArray));
// 가운데 부분 합치고
int from = (nArray/2 == 0) ? nArray-1 : nArray-nArray/2;
int to = (nArray/2 == 0) ? nArray+1 : nArray + nArray/2;
ArrayList<Point> midArray = new ArrayList<Point>(locations.subList(from, to));
// 최소값 갱신
min = Math.min(min, calcMin(midArray));
return min;
}
private static void solve() {
// 입력
Scanner scanner = new Scanner(System.in);
ArrayList<Point> locations = new ArrayList<>();
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
locations.add(new Point(x, y));
}
int min = (int) divide(locations);
System.out.println(min);
}
private static double calcMin(ArrayList<Point> locations) {
double min = Double.MAX_VALUE;
for (int i = 0; i < locations.size() - 1; i++) {
Point p1 = locations.get(i);
Point p2 = locations.get(i + 1);
double distance = Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2);
min = Math.min(min, distance);
}
return min;
}
public static void main(String[] args) {
solve();
}
}
Leave a comment