(JAVA) 백준 2437번 : 저울

 

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

2437번: 저울

 

 

그리디 알고리즘 문제이다.

 

처음에 HashSet 으로 모든 경우의 수를 구하는 코딩을 했더니

시간 초과가 발생했었다..

 

뭔가 잘못되었다 싶어서

 

몇몇 분들의 풀이법을 참고해서

이해한 다음

 

해결했다!

 

 

 

 매커니즘

---

입력 값으로 n개의 저울추의 각 무게를 얻는다.

입력받는 저울추는 무게 순서가 없다.

 

그런데

 

문제에서 요구하는 것은

측정할 수 없는 양의 정수 무게 중 최솟값 이다.

 

무게가 작게 나가는 저울추 들을 가지고 측정할 수 있는 무게를 계산해나가야 한다는 것.

 

 

이후 설명은 예시 입력 값을 가지고 진행하겠다.

 

 

 

Input

7

7 3 1 6 2 7 30 1

 

 

우선, 이 저울추 들을 무게가 작은 순서대로 정렬한다.

 

 

1 1 2 3 6 7 7 30

 

 

그 다음, 앞에서부터 저울추를 하나씩 손에 쥐어보자.

 

 

 

 

1) 1을 손에 쥔다.

 

그럼 이 저울추 1로 측정 가능한 최대의 무게는 ???

 

??? : 1이지!!

이 값을 따로 저장해둔다.

 

 

 

2) 다음 저울추 1을 추가로 손에 쥔다.

 

내 손에는 이전 저울추 1, 지금 저울추 1이 있다.

그럼 이 두 무게추로 측정 가능한 최대의 무게는 ???

 

 

??? : 1, 2 가 가능하니까 2지!!

최대 무게 값을 변경한다.

 

 

 

3) 다음 저울추 2를 추가로 손에 쥔다.

 

내 손에는 이전 저울추 1과 1, 지금 저울추 2가 있다.

그럼 이 세 저울추로 측정 가능한 최대의 무게는 ???

 

 

??? : 이전까지 1과 2가 가능했는데 무게추 2를 가지게 되면 측정 가능한 무게는 1, 2, 3, 4까지 가능하네.

그럼 당연히 최대 무게는 4네!!!

최대 무게 값을 변경한다.

 

 

 

4) 다음 무게추 3을 추가로 손에 쥔다.

 

내 손에는 이전 저울추 1, 1, 2, 지금 저울추 3이 있다.

그럼 이 4개의 저울추로 측정 가능한 최대의 무게는 ???

 

 

??? : 이전까지 1, 2, 3, 4가 가능했는데 저울추 3을 가지게 되면 측정 가능한 무게는 3 + 1,2,3,4까지 가능하네.

그럼 당연히 최대 무게는 3+4 = 7이네!!!

최대 무게 값을 변경한다.

 

 

 

 

규칙을 찾았나요??

 

그리디 알고리즘은 탐욕스러운 알고리즘이기 때문에

이전까지의 결과만을 가지고 최적의 정답을 찾을 수 있습니다.

 

 

4)에서 최대 무게는 7인데, 이 말인 즉슨

1부터 3개를 선택했을 때 나올 수 있는 무게(1 ~ 4) 에서

각각에다 저울추 무게 3을 더하면 4,5,6,7 의 무게가 나올 수 있습니다.

 

 

그럼 만약에

 

4) 에서 3이 아니라 5 이면?

 

저울추 5 하나로 만들 수 있는 5와

5 + 1 ~ 4 = 6, 7, 8, 9 가 나올 수 있으므로 최대 무게는 9가 나옵니다.

 

 

4) 에서 3이 아니라 6 이면?

 

만들 수 있는 최소 무게는 6이 되고

1~4, 6, 7~10 의 무게만 만들 수 있기 때문에

만들 수 없는 최소 무게는 5가 되는 것이죠.

 

 

 

즉, 첫 번째 저울추부터 i 번째 저울추까지 손에 쥐었을 때

 

i - 1번째 저울추까지의 측정 가능한 최대 무게 +1 < i 번째 저울추의 무게  이면

 

정답은 i - 1번째 저울추까지의 측정 가능한 최대 무게 +1 이 되는 것이고

 

 

i - 1번째 저울추까지의 측정 가능한 최대 무게 +1 >= i 번째 저울추의 무게  이면

 

최대 무게 = i - 1번째 저울추까지의 측정 가능한 최대 무게 + i 번째 저울추의 무게  가 되는 것입니다.

그리고 다음 저울추를 손에 쥐러 가는것이구요.

 

 

 

 

감사합니다.

 

 

 

소스코드

---