[SW Expert Academy] 장훈이의 선반

1486. 장훈이의 높은 선반

SW Expert Academy의 문제는 무단 복제가 안되므로 링크로 대체합니다!

장훈이의 높은 선반!

덧셈의 모든 경우의 수를 다 만들어서 원하는 목표인 B부터 차례대로 해당 덧셈이 될 수 있는지 확인하면 됩니다!

덧셈을 확인하는 방법은 어떻게 하면 될까요?

높이 1만이 20명 있을 수 있기 때문에, 우선 배열의 200001의 크기를 가지는 배열을 만듭니다.

그리고 현재는 아무런 더하기도 할 수 없기 때문에 더하기의 max 값은 0 입니다!

이제 3을 입력받겠습니다!

max(0) 에 3을 더해서 3이 더해서 나올 수 있는 것이라는 것을 체크해 줍니다.

이제 4를 입력 받습니다.

max(3)에 4를 더해서 max는 7이 됩니다. 그리고 4도 입력 받았으므로 4에 체크를 해줍니다.

여기서 더하기를 체크할 때 더하기를 할 수 있는지 0 부터 확인하면 아주 큰 문제가 생깁니다!

바로 더했던 부분도 또다시 체크해서 배열 끝까지 체크해버린다는 것이죠!

처음에 1을 입력받았다고 해봅시다!

만약, 가장 작은 값부터 확인하면, 우선 원하는 값인 1이 들어갈 것입니다.

그리고 1이 더하는 것으로 체크되어 있기 때문에 2를 또다시 체크합니다!

결국 끝까지 가버립니다...

이를 위해서는 max까지만 반복문을 돌리는 방법이 있고,

또다른 방법으로는 max부터 확인하는 방법이 있습니다.

저 같은 경우는 2번 째를 사용했습니다.

위 상황에서 3을 입력 받아봅시다.

7이 체크되고!

6이 체크되고!

1에서 4를 체크하고 끝날 것입니다!

이제 나머지는 간단합니다.

B부터 배열을 확인하면서 체크가 되어있다면 그 합이 바로 물건을 꺼낼 수 있는 탑의 최소 높이가 되는 것이죠!

코드를 보실까요?

코드

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

#include<cstdio> #include<cstring>   int people[20], n, B; int max; bool check[200001];   int main() {     int t;     scanf("%d\n", &t);       for (int tc = 1; tc <= t; tc++)     {         memset(check, 0, sizeof(check));         scanf("%d %d\n", &n, &B);         int max = 0;           for (int i = 0; i < n; i++)         {             scanf("%d \n", &people[i]);               for (int j = max; j >= 0; j--)             {                 if (check[j])                 {                     check[j + people[i]] = true;                 }             }               max += people[i];             check[people[i]] = true;         }           int i;         for (i = B; i <= max; i++)         {             if (check[i]) break;         }           printf("#%d %d\n", tc, i - B);     }     return 0; }

이상입니다!

여담

사람이 n명 있다고 한다면, 최악의 경우 20만 번 배열을 n번 검사하게 될 것입니다.

따라서 시간 복잡도는 O(n) 입니다!