1654번 문제 : 랜선 자르기

728x90

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

흠 어려워 보이는 걸

갑자기 알게된 사실 ?

일단 k랑 n을 받으려고

	StringTokenizer st = new StringTokenizer(br.readLine());
		int k = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

이렇게 했다. 한 줄을 읽어서 공백 기준으로 잘라서 각각의 변수에 저장 !

그리고 이미 가지고있는 전선의 길이를 배열에 저장하려고 했는데

for(int i=0;i<k;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

그냥 이렇게 하니까 안 됐음

Y? 다음 줄의 입력을 받아서 st.nextToken으로 찢어야되는데 입력이 없으니까 !

for(int i=0;i<k;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}

요렇게 해야함 !

암튼 그래서 잘 입력 받았고

전선의 갯수와 길이를 입력을 받고 여기서 필요한 갯수만큼을 잘라내서 만들었을 때의 전선의 최대 길이 !

필요한 전선의 갯수를 구할 때까지 반복문

그 안에 배열(이미 갖고있는 전선의 갯수가 들어있는)의 길이만큼 반복을 해서 잘라내는 반복문

{ 어떻게 잘라내냐면 배열의 요소를 끄집어내서 계속 증가하는 수 num으로 나눠

1. 모든 요소를 다 나눌 수 있는지를 조건문으로 검사

2. 다 나눠진다면 나눠진 몫을 count로 헤아려 (흠 그러면 맨 처음 반복문을 while로 해야될 듯)

그 count가 필요한 전선의 갯수랑 같다면 반복문 break;

3. 아 근데 그 중에 최대의 길이를 구해야하니까 max로 최대 전선의 길이를 만족할 때까지 반복을 또 걸어줘야할 듯 ?

대충 구상은 끝 낼 구현해보쟝

3/19

위의 알고리즘에서 수정사항을 거쳐서 햇는데 시간초과가 나와서

1. while문을 true로 계속 반복시켜서 그 안에

for문 하나를 둠.{ 배열 요소의 길이만큼 반복을 할 거고

하나의 배열요소를 계속 증가할 수인 length로 나눠줘서 그 몫을 num에 저장. count라는 변수에 num을 계속 더 해나감.

-> 이 두 줄을 걍 num배열을 없애고 한 줄로 진행. // 이 부분을 한 줄로 바꾸니까 2%진행은 되는데 또 시간초과 나옴.

조건 if (arr[i]/length ==0)이면 어느 한 요소를 나눠서 쓸 수 없는 거니까 continue로 했는데 이게 아닌 break같다.

조건 if(count ==n) 이면{그 안에 if (max < length){ max = length; break; } 전선의 최댓값을 구해.

}// for문 끝

if(length > Array.stream(arr).max().getAsInt())

break; // 나눠줄 길이가 배열의 최댓값 요소보다 커지면 while도 종

}//while문 끝

이렇게 하니까 생각보다 간단하게 문제는 풀었는데 시간초과가 나온다.

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 length = 0; //계속 증가하며 기존 랜선을 잘라낼 랜선의 길이
		int max = 0; //랜선 길이의 최댓값을 비교해주고 저장할 변수
		int count =0; //잘라낸 랜선의 갯수 세기
		int num =0; //length로 나눠져서 생긴 랜선의 갯수
		for(int i=0;i<k;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}//전선의 길이를 배열에 저장
		
		while(true) {
			count = 0;
			length++; //계속 증가하며 배열요소와 나눠줄 전선의 길이
			
				for(int i=0;i<k;i++) {//배열의 길이만큼 반복
					//num = arr[i] / length;
					count+=arr[i] / length; //잘라진 전선의 갯수
					
					if(arr[i] / length == 0)
						break; //랜선의 길이가 잘라낼 랜선의 길이보다 작으면 계속 반복 진행
					if(count == n) {
						if(max < length)
							max=length;
						break; //그냥 끝내면 안 되고 그때의 전선의 길이가 최댓값인지를 구해야함.
					}
				}
				if(length > Arrays.stream(arr).max().getAsInt()) //나눠줄 길이가 배열의 최댓값 요소보다 커지면
					break;
		}
		System.out.println(max);
	}
}

일단 처음 완성 코드

어떻게 하면 시간을 줄일 수 있을까 ?

이문제는 이진탐색을 사용해야한다고 한다 !

와우..... 또 하나 배웠다. 하긴 1씩 늘려서 하는게 의미는 없어보인다. 의미는 있을지 몰라도 시간이 오래걸리니 결국 의미가 없어진다 ! 그럼 이진탐색을 어떻게 구현하는지 알아야겠다

구현
1. 배열을 정렬한다.
2. 중간값을 구한다. mid = (low + high) /2
3. array[mid] 값과 구하고자 하는 key값을 비교한다.
  1. key > mid : low = mid + 1 (왼쪽 반을 버림)
  2. key < mid : high = mid -1 (오른쪽 반을 버림)
  3. key == mid : 구하고자 하는 값을 찾음. → 중간 값 리턴
4. low > high가 될 때까지 1~3 반복

되게 간단한데 이 이진탐색을 어디에 적용해야하냐 ? 바로 length를 1씩 증가해서 비교해주지말고 이진탐색으로 비교.. 인데 그러면 그 값이 담긴 배열이 있어야 하지 않나 ? ㅠ 그거 담는데도 시간이 걸릴 것 같은데 ....

아 ! 그 기준을 배열 요소의 최소값의 중간값으로 잡으면 되겠다 !

후 ㅋ 너무 어지러워서 슬쩍 답안 참고함

BinarySearch에서는 정렬이 필수

아 근데 왜 자꾸 틀렸대 ????????????????????????? 짜증난다

와 .. 자료형으로 long을 안 써줘서 계속 틀렸었따

총 정리 다시 ....

일단 여기서 썼던 배열의 최댓값 구하는 함수

스트림 형태로 만들고 max(), min()을 사용해준뒤 꺼내오면 됨.

Arrays.stream(배열이름).max().getAsInt()

Arrays.stream(배열이름).min().getAsInt()

자료형을 long(8bytes== 64 bit)을 써야했다. (int는 4bytes == 32bit). 조건에 랜선의 길이는 2의 31승 -1 이라고 하였는데

mid를 구할 때 low + high를 하게되면 int의 범위인 2의 31승을 넘기 때문이당.

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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]; //갖고있는 랜선의 길이값을 저장할 배열

		for(int i=0;i<k;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}//전선의 길이를 배열에 저장
		
		Arrays.sort(arr); //랜선 길이값을 오름차순 정렬
		
		int count =0;//잘라낸 전선의 갯수
		long low = 0;
		long high  =arr[k-1];
		long mid;
		while(low <=high) {
			count=0;
			mid = (low+high)/2;
			
			for(int i=0;i<k;i++) 
				count += arr[i] / mid;
			if(count < n) {
				high = mid -1;
			}
			else if(count >= n) {
				low = mid + 1;
			}
		}
		System.out.println(high);
	}
}

이진탐색을 알게된 좋은 알고리즘 !

이진탐색은 정렬 필수 !

근데 마지막...으로 저기 low를 0으로 하면 Run Time Error (/by zero)가 뜬다.. ! ㅜ

1로 해야함 이건 왜인지 잘 모르겠는 걸 ㅠ

0으로 나누면 오류가 난다고 하는데 여기서 나누는 코드는

count += arr[i] / mid; 이거 밖에 없다. 윗줄에서 mid = (low+high)/2 여기서 mid가 0이 나오면 저 런타임에러가 뜨므로 음.. high가 0이되고 low는 0부터 시작하게되면 mid도 0이어서 high가 0이 되어도 에러나는 것을 막기 위해 low를 1부터 시작해줌.

뭐하나 쉬운게 없군

4/11

2805번 나무자르기 문제를 풀 때 이분탐색을 써서 이 글을 다시 참고했다.

그러면서 자료형을 long형으로 설정해야할 일이 있어서 공부해보다가 이것도 다시 풀어보게 되었는데

mid를 일단 long으로 해야하는 건 맞다. 극단적으로 나무의 길이가 2의 31승 -1 이었다고 할 때 high랑 low도 같은 값이었다고 치면 mid는 high+low 하고 /2를 하니까 아직은 안 넘음. 근데 count 조건에 따라 low가 mid+1이 될 때 int자료형 최대값을 넘어버림. 그럼 low가 long형이 되어야하고 low와 high값이 더해져서 mid가 되니까 high도 mid도 그냥 다 long형이어야한다. 근데 틀렸다네 왜

package algorithm;

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

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());
		
		Integer arr[] = new Integer[K];
		for(int i = 0;i<K;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		//이진탐색
		Arrays.sort(arr);
		
		long high = arr[arr.length-1]/2;
		long low = 0;
		long mid = 0;
		while(low<=high) {
			int count = 0;
			mid = (high+low)/2;
			
			for(int i=0;i<K;i++) {
				count += arr[i] / mid;
			}
			if(count < N) {
				high = mid - 1;
			}
			else if(count >=N) {
				low = mid + 1;
			}
		}
		System.out.println(high);
	}
}

아하 저기서 high를 젤 마지막 요소 /2를 해주면 안 됐음

근데 그거 고쳤더니 by zero 오류가 났당. 음 이게 high도 0이고 low도 0일 때 /2를 해서 생기는 오류라 low의 초기값을 1로 해줘야할 것 같다.

전보단 훨씬 수월하게 이해가 되네 끄읏 ~

저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

1920번 문제 : 수 찾기 (0)	2023.03.20
1874번 문제 : 스택 수열 (0)	2023.03.19
1436번 문제 : 영화감독 (0)	2023.03.18
1259번 문제 : 팰린드롬수 (0)	2023.03.17
1018번 문제 : 체스판 다시 칠하기 (0)	2023.03.16