[백준/BOJ] 1654번 : 랜선 자르기 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

---

- 문제 -

 

난이도 실버 3 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

이분탐색을 적용해 푼다.

이분탐색을 사용한건 처음이라 이분탐색에대해 알아보았고, 생각보다 쉽다 생각해 나름대로 적용해서 풀어보았다. 하지만 생각보다 고려해야할 부분들이 많았고, 여러 시행착오를 겪고 성공했다.

 

이분탐색이란 탐색할 범위를 반으로 나누고, 앞과 뒤중 어디에 포함되는지를 확인한 다음 그 범위에서만 다시 확인한다.

범위를 다시 반으로 나누고, 앞과 뒤중 어디에 포함되는지를 확인한 다음 그 범위에서만 다시 확인한다.

일부로 두번말한게 아니다. 그냥 저 행위를 반복하면 된다.

 

여기서 적용할 부분을 자를 랜선 길이가 된다.

랜선 길이는 1~ 최대 랜선 길이가 될 것이고, 이 값들에 이분탐색을 적용한다.

 

예를 들자. 예제 1번을 보면 입력된 랜선 길이중 최댓값을 구한다. 802이다.

그렇다면 출력될 값의 범위는 1 ~ 802가 될 것이다. 그렇다면 이제 이중 가운데 값을 구한다. ((802 + 1) /2)를 해주면 된다. 401이다. 이제 401로 가진 랜선 길이들을 나눠준다. (랜선 길이는 802, 743, 457, 539이다)

(802 / 401 = 2), (743 / 401 = 1), (457 / 401 = 1), (539 / 401 = 1) 이렇게 잘라서 나온 랜선은 총 5개가 된다. 하지만 예제 1번에서 원하는 개수는 11개이다. 그럼 지금 값인 401보다 더 큰 값이 필요하니 작은 값이 필요한지 확인한다. 나눠서 나온 몫까리의 합으로 비교하기 때문에 합이 더 많아지려면 지금 값은 더 작아져야 한다. 그렇다면 1~400 범위를 확인하자.(401부터 확인한 것이기 때문에 그 범위 안에 없으면 -1해서 확인) ((400 + 1) / 2) 해서 200이 된다. 나눠보자. (802 / 200 = 4), (743 / 200 = 3), (457 / 200 = 2), (539 / 200 = 2) 총 11개의 랜선이 나온다. 원하는 개수가 같다. 하지만 문제에서는 11개를 같는 랜선의 길이는 여러가지가 있을 수 있다. 이중 제일 큰 값을 구해달라 했기 때문에 이분 탐색으로 마지막 하나 남는 값까지 전부 다 탐색한 다음 조건을 만족하는 제일 큰 값을 출력한다.

 

코드로 보자.

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	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());
		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[K];
		int end = 0;
		
		for(int i = 0; i < K; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			//입력값중 제일 큰 값을 저장
			if(end < arr[i]) end = arr[i];
		}
		
		//시작은 1부터
		int start = 1;
		//중간 값
		int mid = (end + start) / 2;
		//출력 값을 저장 할 변수이다. 
		//랜선이 하나이고, 필요한 랜선 개수도 1개일 경우 입력 값을 출력해야하기 때문에 최댓값을 저장.
		int result = end;
		
		//남는 범위값이 없어질때까지 반복
		while(end - start >= 0) {
			//랜선 개수의 합을 저장 할 변수, int형을 넘어갈 수 있기 때문에 sum 변수만 long형으로 선언
			long sum = 0;
			
			for(int i = 0; i < K; i++) {
				sum += (arr[i] / mid);
				if(sum > N) break;
			}
			
			//문제를 보면 필요한 개수가 딱맞아 떨어지지 않을 때는 그 이상의 개수중 최솟값으로 구하라 했다.
			//그러니 필요한 개수 이상일때 값들을 result에 저장
			if(sum >= N) {
				start = mid + 1;
				result = mid;
			}else {
				end = mid - 1;
			}
			
			mid = (end + start) / 2;
		}
		System.out.println(result);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.