백준2869, 4948, 2869

백준2869 설탕 배달

설탕 봉지를 최소 개수로 만드는 방법

5 kg 설탕봉지의 개수가 최대로 만들면 됨
1. 5kg 설탕 봉지의 최대 개수는 n // 5 임
전체 설탕 무게 에서 5kg 설탕 봉지 * 봉지 수를 뺀 차가 3kg 로 나누어 떨어져야 한다.

public class Baekjoon2839 {
    public static void main(String[] args) {
        // 1.  입력 받기
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int answer = 0;
        // 2. 5kg 설탕 봉투의 갯수 찾기
        for (int i = n / 5; i >= 0; i--) {
            int temp = n;
            temp -= (i * 5);
            if (temp % 3 == 0) {
                answer = i + (temp / 3);
                System.out.println(answer);
                break;
            }
        }
        if (answer == 0) {
            System.out.println(-1);
        }

    }
}

백준 4948 베르트랑 공준

나의 접근은 n -> 2n 까지 모든 숫자를 소수가 있는지 여부를 일일이 확인할 생각이었다.

for (int i = n ; i <= 2* n + 1; i ++) {
    for (int j = i ; j < n ; j--) {
         if (i % j == 0) {
                   break;
         } 
    // 이런 식으로 정리를 할 생각이었다. 
    }

그러나 1 ≤ n ≤ 123,456 으로

시간 복잡도가 O(n^ 2) 10^6 ^2 = 10 ^ 12 로 시간이 1초를 넘을 가능성이 높다.

그러나 소수는 1 ~ n 사이의 소수를 구할때, 반드시 n까지를 모두 구해야할 필요는 없다.

1 16
**2 * 8
4* * 4
8 * 2
16 *1
위를 보면, p 와 q 중 하나는 결국 n 의 제곱근 보다 작을 수 밖에 없다.

이로 부터 도출할 수 있는 전제는 다음과 같다.
전제

1 ~ n 사이의 소수는 n의 제곱근보다 작다.

네비게이터 분이 찾아준 아리스토테네스의 체를 통해 소수를 찾는 방법을 활용하면 더 시간을 단축할 수 있다.

2부터 N까지의 수를 나열한다.
2부터 가장 작은 수를 소수로 정하고 2의 배수를 모두 지운다.
지우지 않은 수 중에서 가장 작은 수(3)를 소수로 정하고 그 배수(3의 배수)를 지운다.
출처: ~~https://sfida.tistory.com/28~~ [Meezzi 미찌:티스토리]
2 부터 N 까지의 수를 나열해, i = 1씩 커지면서, 소수인지 확인한다.
i 의 배수를 지워나간다. Arr[i] = 0
Arr[i] 값 중 0 이 아닌 수는 소수다.

import java.util.Scanner;

public class Baekjoon4948 {
    public static void main(String[] args) {
        while (true) {
            Scanner scanner = new Scanner(System.in);
            int n  = scanner.nextInt();
            scanner.nextLine();
            System.out.println(getCount(2*n) - getCount(n));
            if (n == 0) {
                break;

            }
        }
    }

    public static int getCount(int n) { // 입력받은 숫자까지의 소수를 계산하는 메소드
        int[] arr = new int[n + 1];
        int c = 0;
        for (int i = 2; i <= n; i++) { // 입력받은 숫자까지의 모든 숫자들을 배열에 초기화한다.
            arr[i] = i;
        }

        int Sqrt = (int) Math.sqrt(n);
        for (int i = 2; i <= Sqrt; i++) { // 제곱근 까지만 계산
            if (arr[i] == 0) { // 0으로 초기화 되어있는 숫자들은 건너뛴다.
                continue;
            }
            for (int j = i + i; j <= n; j += i) { // 현재 숫자(i)를 제외한 i의 배수들은 모두 소수가 아니므로 -> arr[i] = 0
                arr[j] = 0; // 0이 들어있는 번지는 소수가 아니다.
            }
        }
        for (int i = 2; i <= n; i++) {
            if (arr[i] != 0) {
                c++;
            }
        }
        return c;
    }

    }

백준 2869 달팽이는 올라가고 싶다

문제 방향
함께 pair-coding 을 해주셨던 Navigator 분이 식을 잘 써주셔서 수월하게 풀렸으나, 좀 더 이해가 필요했다.

달팽이는 낮에 a 만큼 올라가고
달팽이는 밤에 b 만큼 내려간다.
총 올라가야 하는 거리는 v 다.

A = 2, B = -1, v = 5
낮 1 높이 = 2
밤 1 높이 = 2 - 1
낮 2 높이 = 2 - 1 + 2
밤 2 높이 = 2 -1 + 2 - 1
낮 3 높이 = 2 -1 + 2 - 1 + 2

중요한 전제를 확인하면

달팽이는 무조건 낮에 v 목표한 높이를 초과하게 된다.
하루동안 낮 1 -> 낮 2 은 ( 2 -1 ) 만큼 올라가게 된다.
하루가 지날때마다 a- b 만큼 커지는 등차 수열과 같다.

그렇다면 다음 과 같은 등차 수열로 정리할 수 있다.
A = 낮에 올라간 거리
B = 밤에 내려간 거리
N = number of days

v >= (a-b) *( n-1 ) + a

하지만 우리가 알고 싶은 건 N 며칠 째에 달팽이가 v 를 넘는가?
N 에 대한 식으로 다시 쓰면,
N <= (v -a ) / (a -b ) + 1

그러나 이렇게 하면 다음 예제의 답을 구할 수 없다.
A = 5, b = 1, v = 6
값을 대입해보면,
N = (6-5) / (5-1) + 1
Java 는 int / int -> int 로 계산하기 때문에 소수점을 버림하게 된다.
N = 0 + 1 = 1
따라서, (v-a) / (a -b ) 나누어 떨어지는 경우와 나누어 떨어지지 않는 경우를 분기처리해줘야 한다.

(V -a ) % (a - b) == 0 인 경우, (v -a ) / (a -b ) + 1
(V -a ) % (a - b) != 0 인 경우, (v -a ) / (a -b ) + 2

import java.util.Scanner;

public class Baekjoon2869 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int v = scanner.nextInt();

//        v <= (a -b) * (n - 1) + a
        if ((v - a) % (a - b) == 0) {
            System.out.println((v - a) / (a - b) + 1);
        } else {
            System.out.println((v - a) / (a - b) + 2);
        }
    }
}

yuxiu dev.log

백준2869, 4948, 2869

백준2869, 4948, 2869

백준2869 설탕 배달

백준 4948 베르트랑 공준

백준 2869 달팽이는 올라가고 싶다

댓글

티스토리툴바