백준 자바 2805 알고리즘 '나무 자르기 문제' 문제풀이





날씨가 많이 쌀쌀해졌군요

추운 날씨속에 학교 앞 자취방에서 코딩을 해봅니다.




코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 2805번 문제 링크

More info: 나무자르기 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘




첫번째 시도 (시간초과로 틀림)

Procedure findMaxH(long[] a, long p, long r, Long m)

Inputs :
- a : the array to search in
- p : the value we are searching for in a(min) m의 촤소값
- r : the value we are searching for in a(max) m의 최대값
- m : the value we are searching for in a(equal) 잘라야하는 나무의 값

Outputs :
- 잘라야하는 나무 산출량의 최대 높이

  1. 최소값을 0, 최대값을 나무의 최대크기로 정한다.
  2. 최소값 + 최대값의 평균값인 q를 구한다.
  3. q 값일때 나무 산출량을 H를 ValueOfTreeOutput을 통해 구한다.
    a) H가 m 보다 크면 최소값을 q+1로 수정한다
    b) H가 m 보다 작으면 최대값을 q-1로 수정한다
    c) H와m이 같다면 q를 반환한다.
  4. recursive 재귀적으로 돌린다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.Scanner;

public class Main {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Long M = sc.nextLong();
long a[] = new long[N];
long maxLength = 0;


for(int i = 0; i<N; i++){
//Tree length
a[i] = sc.nextLong();
maxLength = Math.max(a[i],maxLength);
}

System.out.println(findMaxH(a, 0, maxLength, M));
}


private static long findMaxH(long[] a, long p, long r, Long m) {
long q = (p+r)/2;

long H = ValueOfTreeOutput(a, q);

if (H > m){
return findMaxH(a,q+1,r,m);
}

else if (H < m){
return findMaxH(a,p,q-1,m);
}

else{
return q;
}
}

private static long ValueOfTreeOutput(long[] a, Long H) {

long sum = 0;

for(int i = 0; i<a.length; i++){

long temp = a[i] - H;

if(temp > 0){
sum += temp;
}
}
return sum;
}
}








n번째 시도 (성공)




위에 코드에서

자바 배열을 오름차순으로 정렬


1
Arrays.sort(a);


재귀문 삭제


While 문 사용을 통해 시간을 줄였습니다


기본적인 틀은 binary search를 사용한다는 점에서 같습니다

문제에서 제시된 값이

매우 크기 때문에 조그마한 차이도 크게 느껴지는것 같습니다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();

int []a = new int[N];

for(int i = 0; i<N; i++){
//Tree lengths
a[i] = sc.nextInt();
}

Arrays.sort(a); // 자바 배열을 오름차순으로 정렬

int p = 1;
int q;
int r = a[N-1];
long CalculatedOutPut = 0;
long GivenOutPut = M;

while (p <= r)
{
q = (p + r)/2;
CalculatedOutPut = 0;

for(int i = 0; i<N; i++){
if(a[i] >= q){
CalculatedOutPut += (a[i] - q);
}
}

if(CalculatedOutPut >= GivenOutPut){
p = q + 1;
}
else if(CalculatedOutPut < GivenOutPut){
r = q - 1;
}

}

System.out.println(r);
}



}




글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

모두들 화이팅 하셔서 훌륭한 프로그래머가 되시길 바라겠습니다.






Author

Song Kim

Posted on

2020-10-04

Updated on

2020-10-04

Licensed under

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments