16일차 사전캠프

오늘도 알고리즘 스터디를 진행했다

 

4948번 베르트랑 공준

자연수 n에 대하여 n보다 크고 2n보다 작거나 같은 소수는 적어도 하나 존재한다!라는 베르트랑 공준을 증명하는 문제로

public class Main {
public static boolean arr[];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        arr = new boolean[123456*2 + 1];
        era(123456*2);
        while(true) {
          int n = Integer.parseInt(bf.readLine());
          if(n==0) {
          break;
          }
          sb.append(countDecimal(n)).append("\n");
        }
        System.out.println(sb);
     
    }
    public static void era(int n) {
     arr[0] = arr[1] = true;
     for(int i=2;i<=Math.sqrt(n);i++) {
     if(!arr[i]) {
     for(int j = i * i; j<= arr.length;j = j + i) {
     arr[j] = true;
     }
     }
     }
    }
    public static int countDecimal(int n) {
     int count = 0;
     for(int i=n+1;i<=n*2;i++) {
     if(!arr[i]) {
     count++;
     }
     }
     return count;
    }
}

 

 

소수를 판정하는 방법은 단순하게 1~n까지 직접 나눠서 구하는 방식과
1~ 루트n까지 직접 나눠서 구하는 방식
마지막으로 에라토스테네스의 체를 이용하는 방식으로 알고있는데

이 경우 최대 123456 * 2 인 246912까지 구해야 하기 때문에 범위가 큰 경우 에라토스테네스의 체를 이용하는게 제일 좋으므로 에라토스테네스의 체를 이용해서 구현

에라토스테네스의 체는
2부터 시작해서 소수의 배수를 모두 지우는 식의 알고리즘으로
소수가 아니면 true로 구현!

 

 

1002번 터렛

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int arr[] = new int[1001];
        int count[] = new int[1001];
        st = new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        int totalW = 0;
        int time = 0;
        int a = 0;
        while(a!=n) {
            if(totalW + arr[a] <= L) {
           		totalW += arr[a];
           	}
           	else {
           		a = a -1;
           	} 	
        	for(int j=0;j<=a;j++) {
        		count[j]++;
        	}
        	for(int j=0;j<n;j++) {
        		if(count[j]==w) {
        			totalW -= arr[j];
        		}
        	}
        	a++;
        	time++;
        }
        System.out.println(time+w);
    }
}

 

 

각각 2개의 원이 생기는데 이 원들이 겹치는곳이 상대편 마린이 있을 수 있는 좌표의 위치이므로
원이 겹칠 수 있는 경우의 수는
1. 아예 안만나는 경우의 수
그 중 두 원이 떨어져 있어서 못만나는 경우의 수
두번째로 한 원이 다른 원 안에 있어서 못만나는 경우의 수

2. 접하는 경우의 수 즉 1번만 만나는 경우의 수
원이 외접 또는 내접할 때

3. 원이 2곳에서 만나는 경우의 수

4. 마지막으로 좌표와 거리가 모두 일치하는 만나는 수가 무한대인 경우의 수

총 6가지로 구분된다.

 

 

 

1002번 터렛

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int arr[] = new int[1001];
        int count[] = new int[1001];
        st = new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        int totalW = 0;
        int time = 0;
        int a = 0;
        while(a!=n) {
            if(totalW + arr[a] <= L) {
           		totalW += arr[a];
           	}
           	else {
           		a = a -1;
           	} 	
        	for(int j=0;j<=a;j++) {
        		count[j]++;
        	}
        	for(int j=0;j<n;j++) {
        		if(count[j]==w) {
        			totalW -= arr[j];
        		}
        	}
        	a++;
        	time++;
        }
        System.out.println(time+w);
    }
}

 

이런식으로 풀었는데 큐를 이용해서 푸는 방법이 훨씬 쉬워보였다. 나중에 큐를 이용해서 한번 더 풀어보자!