[BOJ] 2437. 저울(Greedy, 탐욕 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

그리디는 최적의 상태가 존재하는지, 어떤 규칙이 존재하는지 먼저 확인해보아야 한다.

입력된 저을추의 무게가 아래와 같다면

3 1 6 2 7 30 1

먼저 정렬을 해줄 필요가 있다.

1 1 2 3 6 7 30

1부터 만들 수 있는 양의 정수 무게를 확인해보자.

1 -> 1

2 -> 2

3 -> 3

4 -> 3 + 1

5 -> 3 + 2

6 -> 6

7 -> 7

8 -> 7 + 1

...

규칙을 잘 찾아보자.

이전 상태까지 만들 수 있는 무게 W가 있을 때,

이 무게 W + 1이 그 다음 무게추보다 크거나 같다면

계속 이 무게를 쌓아나갈 수 있다.

예를 들어

현재 무게추는 1 1 2 3 6 7 30 이고,

지금까지 만들 수 있는 최저 무게(W)는 0이라고 했을 때

1 <= W(0) + 1 이 true이므로 W(0)에 1을 쌓을 수 있다. W(1)

계속 동작해보면

1 <= W(1) + 1 은 true, W(1) + 1 = W(2)

2 <= W(2) + 1 은 true, W(2) + 2 = W(4)

3 <= W(4) + 1 은 true, W(4) + 3 = W(7)

6 <= W(7)  + 6 은 true, W(7) + 6 = W(13)

7 <= W(13) + 1 은 true, W(13) + 7 = W(20)

30 <= W(20) + 1 은 false, 이므로 break;

여기서 지금까지 만들 수 있는 최저 무게는 W(20)이므로

측정할 수 없는 양의 정수 무게 중 최솟값은

W(20) + 1 인 21이 된다.

#. Code

1 2 3 4 5 6 7 8 9 10

N, A = int(input()), sorted(list(map(int, input().split())))   W = 0 for i in A:     if i <= W + 1:         W += i     else:         break   print(W+1) Colored by Color Scripter

cs

line 5) 지금까지 만들 수 있는 최저 무게 W + 1 이 현재 가지고 있는 무게추보다 크거나 같다면,

line 6) W에 가지고 있는 무게추의 무게를 더해준다.

line 7) 그렇지 않을 경우

line 7) break