알고리즘 공부 1일차

문제 1) 2839 

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

N 이 주어짐 

N의 범위는 3~5000

봉지는 5키로 3키로

N이 주어짐 일단 5로 나눔

5키로그램 갯수 = M
3키로그램 갯수 = M2
case 1) 4로 나누어 떨어짐

case 2) 3으로 나누어 떨어짐

case 3) 2로 나누어 떨어짐

case 4) 1로 나누어 떨어짐

case 5) 0으로 나누어 떨어짐

case 1) M-1 M2 3개

case 2) M + M2 1개

case 3) M-2 M2 4개

case 4) M-1 M2 2개

case 5) M

import java.util.Scanner;

public class P2839 {
    public static void main(String[] args) {
        // write your code here
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = N%5;
        int M = N/5;
        int M5 = 0;
        int M3 = 0;
        int result =0;
        switch(K){
            case 4:
                M5 = M-1;
                M3 = 3;
                break;
            case 3:
                M5 = M;
                M3 = 1;
                break;
            case 2:
                M5 = M-2;
                M3 = 4;
                break;
            case 1:
                M5 = M-1;
                M3 = 2;
                break;
            case 0:
                M5 = M;
                break;
        }
        if(M5<0){
            if(N%3 == 0){
                result = N/3;
            }else{
                result = -1;
            }
        }else {
            result = M5+M3;
        }
        System.out.println(result);
    }
}

문제2) 4948

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

 

N이 주어짐
N~ 2N 사이에 있는 소수 출력
함수 내용
N 을 받아서 N ~ 2N 까지 소수를 탐색함 만약 소수라면 출력 아니라면 다음

for i = N ; i<=2N; i++{
N 을 소수 판별
만약 소수라면 count ++
}
count 출력

import java.util.Scanner;
public class P4948 {
    public static void main(String[] args) {
        int N = 1;
        Scanner scanner = new Scanner(System.in);
        while(N!=0){
            N = scanner.nextInt();
            boolean answer = false;
            int count = 0;
            for (int i = N; i <= 2 * N; i++) {
                answer = isPrime(i);
                if (answer == true) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    public static boolean isPrime(int n) {
        int result = 0;
        if(n <= 2){
            return true;
        }
        for(int i = 2; i<n;i++){
            result = n%i;
            if(result == 0){
                return false;
            }
        }
        return true;
    }
}

 

문제3) 2869

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

A B V

A미터 올라감 B미터 미끄러짐 V 높이
heightNow 현재 높이

while(V<현재 높이) 면 등반 종료

A 만큼 올라감 Day 1 증가 heightNow = A + heightNow
만약 (V<현재 높이면) 등반 종료
B만큼 떨어짐 heightNow = heightNow - B
X

 A-B 하루만에 올라가는 높이
V-B 그날 아침에 도착하는 높이

V-B / A-B 깔끔하게 나누어 떨어지면 상관 x 
 소수점 단위가 남으면 하루 부족한 것이므로 + 1

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        int V = scanner.nextInt();
        int Day = 0;

        Day = (V-B) / (A-B) ;

        if((V-B)%(A-B) !=0 ){
            Day++;
        }

        System.out.println(Day);
    }
}