🔗 링크

https://programmers.co.kr/learn/courses/30/lessons/42886

⚖️ 문제

저울추가 담긴 배열이 있을 때(weight),

이 저울 추들을 조합해서 만들 수 없는 최솟값을 구해야한다.

예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

👀 예제로 문제 파악하기

입력 : weight [1, 2, 3, 5]

1, 2, 3 → 가능

4 → 가능 (3 + 1)

5 → 가능

6 → 가능 (1 + 5)

7 → 가능 (2 + 5)

8 → 가능 (3 + 5)

9 → 가능 (5 + 3 + 1)

10 → 가능 (5 + 3 + 2)

11 → 가능 (5 + 3 + 2 + 1)

= 만들 수 없는 최솟값은 12이다. (누적값 + 1)

입력 : weight [1, 2, 3, 10]

1, 2, 3 → 가능

4 → 가능 (3 + 1)

5 → 가능 (3 + 2)

6 → 가능 (3 + 2 + 1)

= 만들 수 없는 최솟값은 7이다. (만약 누적된 값보다 다음 값이 더 크면, 계산을 멈추고 누적값 + 1)

😮 알고리즘 풀이 순서

1. 배열 weight를 정렬한다.
2. 누적값을 담을 sum을 배열의 0번째로 초기화한다.
3. 배열 weight만큼 반복문을 돌린다.
   • i의 초기화 값은 1이다. (이미 0번째는 sum에 있기 때문)
4. 만약 누적값(sum)보다 i의 다음 값보다 작으면, 반복문을 종료한다.
   • i의 다음 값이 없어 배열 범위를 벗어나는 예외 발생 방지를 위해, i가 weight - 1과 다르다는 조건도 건다.
5. 반복문이 종료되면 sum + 1을 return 한다.
   
   

👨‍💻 코드

public class Solution {
 public int solution(int[] weight) {
 
    Arrays.sort(weight);
    int sum = weight[0];

    for (int i=1; i<weight.length; i++){
      sum += weight[i];

      if (i != weight.length - 1 && sum < weight[i+1]) break;
    }

    return sum + 1;
  }

  @Test
  public void 정답(){
    Assert.assertEquals(21, solution(new int[]{3, 1, 6, 2, 7, 30, 1}));

  }
}