백준) 수학, 이분 탐색

1978번 소수 찾기

---

내가 떠올린 풀이 해설

소수를 찾는 기본 문제이다. 소수를 찾기 위해 아래의 코드를 추가시켰다.

for(int j = 2; j < arr[i]; j++) {
   if(arr[i] % j == 0) {
      isPrime = false;
      break;
   }

위의 코드 if문이 실행되면 소수가 아니므로 isPrime에 false를 하고 break로 빠져나왔다. 마지막에 만약 isPrime이면 cnt를 늘려주는 식으로 소수의 개수를 구했다.

---

정확한 풀이

import java.util.*;
public class Baek1978 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n  = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0 ; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			boolean isPrime = true;
			if(arr[i] == 1) {
				continue;
			}
			for(int j = 2; j < arr[i]; j++) {
				if(arr[i] % j == 0) {
					isPrime = false;
					break;
				}
			}
			if(isPrime) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

---

1654번 랜선 자르기

---

내가 떠올린 풀이 해설

변수의 크기를 고려해서 변수를 선언해야 된다. 그렇지 않으면 답이 틀렸다고 나온다. 이 문제 또한 기본 이분 탐색 문제이다. 렌선의 최소 길이인 1로 start를 잡고 end는 렌선 배열의 최대 값을 선언해준다.  while문에서 start가 end보다 작거나 같을 때까지 반복한다. while문 안에서 이분 탐색으로 총 만들 수 있는 개수를 구해주면 된다.

---

정확한 풀이

import java.util.*;
import java.io.*;

public class Baek1654 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int k = Integer.parseInt(st.nextToken());
		long n = Long.parseLong(st.nextToken());
		
		long[] arr = new long[k];
		for(int i = 0; i < k; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		Arrays.sort(arr);
		
		long start = 1;
		long end = arr[k - 1];
		long mid = 0;
		
		while(start <= end) {
			mid = (start + end) / 2;
			int sum = 0;
			for(int i = 0; i < k; i++) {
				sum += arr[i] / mid;
			}
			if(sum < n) {
				end = mid - 1;
			}
			else {
				start = mid + 1;
			}
		}
		System.out.println(end);
	}
}

---

오늘의 회고

기본 문제들이라 문제를 해결하는데 어려움은 없었습니다.

제가 이번에 스터디에 참여하게 되었습니다. 주제를 잡고 스터디하는 것이 아니라 모여서 각자 코딩하고 어떤 공부를 하는지 이야기하는 모임입니다. 일요일에 처음 참여하게 되었는데 앞으로도 다른 스터디나 스터디를 꾸준히 할 생각입니다. 스터디에 참여하게 된 이유는 따로 같은 분야에 계신 선배님들을 만날 기회가 없고 스터디 카페에 박혀있어 우울해지는 것 같아 참여하게 되었습니다. 스터디에 계신 분들도 다 저보다 연차가 높은 선배님들이라 열심히 배우겠습니다. 내일은 프로그래머스 중간고사가 있어서 중간고사 시험을 보고 오겠습니다. 중간고사 문제는 외부로 유출이 안돼서 블로그에 작성은 하지 못할 것 같습니다.