[JAVA] 1654번 - 랜선 자르기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

K개의 랜선을 잘라서 자른 랜선의 길이가 N개 이상 되어야한다.

 

완전 탐색 O(N)

주어진 랜선K개들을 잘라서 N개의 랜선을 만들어야하는데

랜선길이 1cm부터 최대길이까지 하나하나 보게되면

각 랜선의 길이는 최대 2^31 -1이니까 약 21억까지 될 수 있음 

 

이분 탐색 O(log N)

(log2 2^31)이니까 약 31번 비교해서 가능

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. T를 입력받아 T만큼 반복을 수행한다

2. N,M을 입력받고 각각의 크기 만큼 arr,brr배열에 숫자들을 넣어준다

3. 두 배열을 모두 정렬한다

4. brr만큼 반복문을 돌면서  A가 B보다 큰 쌍의 개수를 구한다

 

그리고 몰랐던 부분

• 랜선의 길이가 짧아지면 → 만들 수 있는 랜선의 개수가 늘어난다
• 랜선의 길이가 커지면 → 만들 수 있는 랜선의 개수가 줄어든다

그래서 mid의 값으로 만들 수 있는 랜선의 개수를 구하고

• 이 때 랜선의 개수가 N보다 작다면 ?
  • 더 많은 랜선을 만들어야 합니다.
  • 그래서 더 짧은 길이의 랜선을 탐색해야합니다
  • 왼쪽을 다시 탐색해줍시다.
• 이 때 랜선의 개수가 N보다 크거나 같다면?
  • 탐색을 탈출하지 않고 정답 값을 업데이트 한 뒤 더 긴 길이의 랜선을 탐색합니다.
  • 정답이 “최대”길이의 랜선을 구하는 것이기 때문에 더 가능한 긴 길이가 있는지 탐색해야 합니다.
  • 오른쪽을 다시 탐색합니다.

오.. 왜 이분탐색으로 풀어야하는지 몰랐는데 첨알았다 

++그리고 long타입으로 해야 오류안난다

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

이분탐색말고 그냥 구현

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 sum=0;
        
        for(int i=0; i<k; i++) {
        	arr[i] = Integer.parseInt(br.readLine());
        	sum+=arr[i];
        }
        
        int max=(int) sum/n; //j가 231
     
        int result = 0;
        
        for(int i=max; i>0; i--) {
        	   int cnt=0;
        	for(int j=0; j<k; j++) {
        		cnt+=arr[j]/i;
        	}
        	if(cnt>=n) {
        		result=i;
        		break;
        	}
        }
        System.out.println(result); 
    }
}

 

 

 

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];
 
        long high = 0;
        
        for(int i=0; i<k; i++) {
        	arr[i] = Integer.parseInt(br.readLine());
        	if(high<arr[i]) {
        		high = arr[i];
        	}
        }
        
        long low = 1;
        
        while(low<=high) {
        	long mid = (low+high)/2;
        	long cnt=0;
        	
        	//현재 길이로 만들 수 있는 랜선의 길이
        	for(int i=0; i<arr.length; i++) {
        		cnt+=(arr[i]/mid);
        	}
        	// 랜선의 개수가 n보다 작으면(길이가 답보다 길어서 그런거임)
        	// 더 많은 랜선을 만들어야함 
        	// 왼쪽을 탐색해야함 
        	if(cnt<n) { 
        		high = mid-1;
        	}
        	//랜선의 개수가 n보다 많다(길이가 답보다 짧으니까 늘려야함)
        	//오른쪽 탐색 
        	else {
        		low = mid+1;
        	}
        		
        }
        System.out.println(high);
    }
}