[SW Expert] #1486. 장훈이의 높은 선반

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

먼저 전에 가능한 시험 점수라는 문제를 풀면서 가능한 모든 점수를 구하는 문제를 푼 기억이 있어서 같은 방법으로 해결하면 좋겠다 라는 생각을 하였다. 가능한 시험 점수라는 방법으로 문제를 해결했으나, 깔끔한 코드가 아닌 것 같아서 다른 방법이 존재할까 찾아보았고 dfs로 가능하다는걸 알았다. 어렵지 않았는데 왜 dfs로 해결해볼까?라는 생각을 하지 못했다.

---

2. 코드

#include<iostream>
#include<string.h>
using namespace std;
	int test_case;
	int N;
	int top_height;
	int array[300000];
	int temp = 0;
	int sum = 0;
	int result = 0;
int main(int argc, char** argv)
{
    cin>>test_case;
	for(int i = 1; i <= test_case; i++)
	{
		cin >> N;
        cin >> top_height;
            memset(array, 0, sizeof(array));
        array[0] = 1;
       	for(int j = 0; j < N; j++){
            cin >> temp;
            sum += temp;
            for(int k = sum; k>=0; k--){
             if(array[k] != 0){
                 array[k + temp]++;
             }
            }
        
        }
        
         for(int m = 0; m< 300000; m++){
         if(array[m] !=0 && m >= top_height){
         	result = m - top_height;
                              break;
         }
        }

        
        cout << "#"<<i<<" "<< result << endl;
    }
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}