[백준] 2805번 나무 자르기 (투포인터_JAVA)

2024. 1. 17. 17:29· [자료구조] 알고리즘
목차
  1. 문제
  2. 설계
  3. 알고리즘 설계 [접근 방법] : 투포인터
  4. 풀이 과정
  5. 코드

int 범위 잘못봐서 틀린사람 바로 나!

...

문제를 꼼꼼히 읽자고 아무리 다짐해도

왜 자꾸 이런 거에서 틀리는지

 

그래도 9개월 전에 틀린 문제

오늘 맞혀서 기분이 굉장히 좋다!

 

 


문제

 

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

 

 


설계

 

알고리즘 설계 [접근 방법] : 투포인터

나무의 개수가 백만 이하여서, 완전탐색은 시간초과가 발생할 것이라 생각했다.

그래서 고민하다가, 문득 산하언니가 비슷한 문제를 투포인터로 풀었다고 설명해준 게 생각나서 투포인터로 풀었다.

확실히 투포인터로 풀으니 시간이 많이 줄었다.

 

풀이 과정

1.

나무의 개수와 가져가고 싶은 나무의 길이를 입력받는다.

여기서 중요한 점은 나무의 길이가 20억 이하로 입력될 수 있으므로 int가 아닌 long으로 입력받아야 한다.

 

2.

각각의 나무의 길이를 입력받기 위해 배열 tree를 생성하고 입력받는다.

가장 긴 나무의 길이를 알기 위해 입력받을 때마다 max를 갱신시킨다.

 

3.

min은 0, max는 가장 긴 나무의 길이로 설정한다.

그리고 min이 max보다 작거나 같을 때만 반복문을 실행하도록 조건을 만들고, 중간값 mid를 구한다.

이 mid값이 나무를 자르는 높이다.

 

4.

mid를 기준으로 나무를 잘랐을 때의 나무의 길이 합인 sum을 구한다.

 

이 sum의 값이 원하는 길이인 length보다 작다면, 더 작은 높이로 잘라야 하므로 max값을 mid-1로 갱신해준다.

만약 sum의 값이 원하는 길이와 같거나, 크다면 더 높게 자르는 것을 시도할 수 있으므로 min값을 mid+1로 갱신한다.

또한, answer의 값을 mid와 비교한 후 더 큰 값으로 answer을 갱신한다.

왜냐하면 우리는 원하는만큼만 나무를 자르고 싶기 때문에, 나무를 자르는 높이가 높을 수록 좋기 때문이다. 

 

5.

반복문이 종료되면 가장 최적의 높이인 answer를 출력한다

 

 


코드

 

import java.util.Arrays;
import java.util.Scanner;

public class Test_2805_나무자르기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();			//나무의 개수
		long length = sc.nextLong();	//가져가고 싶은 나무의 길이
		
		long min = 0;
		long max = 0;
		
		long[] tree = new long[n];
		for(int i=0; i<tree.length; i++) {
			tree[i] = sc.nextLong();
			if(max<tree[i]) max = tree[i];
		}
		
		long answer = 0;
		
		//투포인터
		while(min<=max) {
			long mid = (min+max)/2;
			
			long sum = 0;
			for(int i=0; i<tree.length; i++) {
				if(mid <= tree[i]) sum+=(tree[i]-mid);
			}	
			
			if(sum<length) max = mid-1;			//원하는 만큼 나무가 잘리지 않았을 때
			else {								//원하는 것 이상 나무가 잘렸을 때
				min = mid+1;
				answer = Math.max(mid, answer);
			}
		}
		
		
		//출력
		System.out.println(answer);
				
	}
}

 

 

(❁´◡`❁)

끝!

 

 

'[자료구조] 알고리즘' 카테고리의 다른 글

[백준] 16928번 뱀과 사다리 게임 (BFS_JAVA)  (1) 2024.01.19
[백준] 1541번 잃어버린 괄호 (그리디 알고리즘_JAVA)  (0) 2024.01.18
[프로그래머스] 리코쳇 로봇 (BFS_JAVA)  (0) 2024.01.16
[백준] 1463번 1로 만들기(DP_JAVA)  (0) 2024.01.14
[백준] 18111번 마인크래프트 (완전탐색_JAVA)  (0) 2024.01.12
  1. 문제
  2. 설계
  3. 알고리즘 설계 [접근 방법] : 투포인터
  4. 풀이 과정
  5. 코드
'[자료구조] 알고리즘' 카테고리의 다른 글
  • [백준] 16928번 뱀과 사다리 게임 (BFS_JAVA)
  • [백준] 1541번 잃어버린 괄호 (그리디 알고리즘_JAVA)
  • [프로그래머스] 리코쳇 로봇 (BFS_JAVA)
  • [백준] 1463번 1로 만들기(DP_JAVA)
콩지연
콩지연
콩지연
콩알탄의 코딩 실력 폭발 도전기
콩지연
전체
오늘
어제
  • 분류 전체보기 (77)
    • [자료구조] 알고리즘 (55)
    • [CS] 네트워크 (1)
    • 백엔드 (11)
    • 자바 (0)
    • 다양한 후기 (0)
    • 영어 (1)

인기 글

최근 글

hELLO · Designed By 정상우.v4.2.1
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.