728x90
반응형
https://www.acmicpc.net/problem/2437
2437번: 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓
www.acmicpc.net
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main {
public static int n;
public static Integer []arr;
public static long sum=0;
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
arr=new Integer[n];
StringTokenizer st=new StringTokenizer(br.readLine());
int cnt=0;
for(int i=0;i<n;i++){
arr[i]=Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
cnt=0;
for(int i=0;i<n;i++){
if(cnt+1>=arr[i]){
cnt+=arr[i];
}
}
System.out.println(cnt+1);
}
}
|
cs |
코드만 보면 진짜 쉬운 것 같은데 누적합을 그리디로 어떻게 구현해낼 것 인가를 생각하는게 어려웠다.
처음에는 이진탐색으로 풀었.다...ㅋㅋ(물론 틀림)
위 사진의 코드를 기준으로 얘기하겠다. (어차피 둘다 똑같긴 하다.)
추로 만들 수 없는 크기중 가장 최소이니까 계속 누적해서 더한다음 거기다 1을 더해주면 최소의 크기가 되지 않을까?라는 생각이 1차적인 생각이다.
결국 지금까지 누적한게 (cnt) 추의 무게 보다 크거나 같다면 추로 무게를 측정할 수 있다는 말이니까 cnt에 추의 무게도 더해준다.
cnt가 결국에 추로 만들수 있는 무게를 의미한다.
그렇다면 왜 cnt에 초기값으로 1을 뒀을까? 에 의문을 가질 수 있는데 결국 문제를 잘 읽어보면 "측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다."라는 문장이 있다.
만약
2
2 4
이런식으로 테케가 있다고 가정했을 때 이 둘로 만들 수 없는 양의 정수 무게 중 최소값은 1이될 것이다. 양의 정수중 가장 작은 값이 1이기 때문에.
728x90
반응형
'알고리즘 > 그리디' 카테고리의 다른 글
| [java 백준] 골드 5/ 11000번 강의실 배정 (0) | 2022.08.06 |
|---|---|
| [C 백준] 실버 4/ 13305번 주유소 (0) | 2022.03.11 |
| [java 백준] 실버 2/ 1541번 잃어버린 괄호 (0) | 2022.02.15 |
| [java 백준]골드 4/ 1744번 수묶기 (0) | 2022.02.11 |
| [java 백준] 실버 2/1931번 회의실 배정 (0) | 2022.02.08 |
댓글