[ 백준 BOJ ] 10564번 - 팔굽혀펴기(C++)

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

 

생각 흐름

• 가장 먼저 생각한 것은 dfs였다. 점수의 순서가 중요하다고 생각했기 때문이다. 하지만 시간 초과를 피할 수 없어 보여 바로 그만뒀다.
• 이분탐색도 생각해봤는데, mid의 값을 left 또는 right에 할당해줄 때의 기준이 애매해서 접었다.
• 웬만한 알고리즘 생각해봤는데 답이 안 서길래 DP로 접근해보기로 했다.
• 처음에 세운 점화식은 vector<int> dp[5001]와 dp 배열을 만들고, dp[i]에는 득점 점수의 최대값을 이루는 얻은 점수의 리스트이다. 예제의 첫 번째의 경우 dp[29] = {3, 2, 2, 7}와 같은 꼴을 말한다.
• 그렇게 하고 4번째 예제를 넣었는데 이상한 값이 떴다. 정답은 1,1,1이어야 한다. 즉, dp[6]={1,1,1}이어야 하고 dp[3]={1,1}이어야 한다. 하지만 점수가 3으로 주어지므로 dp[3]={3}이 초기값으로 들어가져 있고 1+1보다 3이 더 크므로 {1,1}이 저장되지 않는다.
• 그렇게 dp[n]이 여러 버전이 있어야 겠다 싶어서 vector<vector<int>> dp[5001]와 같이 만들고 제출했고 메모리 초과를 받았다.
• 메모리 초과를 받은 시점이 문제를 풀지 2시간이 지난 시점이기에 답지를 본 결과 dp[득점 점수][n]와 같이 세우는 것을 보았다. 본인의 점화식의 경우에도 그냥 vector<int>를 [득점 점수]에 넣었으면 됐던 것이다. 너무 생각을 안 하고 풀었던 것 같다.
• dp 배열을 변경하고 로직도 살짝만 건든 후 제출했더니 맞았다.

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <memory.h>

using namespace std;

int T, N, M;
vector<int> input;
bool dp[1000][5001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>T;
    
    while(T--){
        cin>>N>>M;
        input.clear();
        for(int i = 0; i<M; i++){
            int tmp;
            cin>>tmp;
            
            input.push_back(tmp);
            dp[tmp][tmp] = true;
        }
        
        for(int i = 1; i<N; i++){
            for(int j = 1; j<1000; j++){
                if(!dp[j][i]) continue;
                for(int k = 0; k<input.size(); k++){
                    if(i+j+input[k]>N) continue;
                    dp[j+input[k]][i+j+input[k]]=true;
                }
            }
        }
        
        int answer = -1;
        
        for(int i = 999; i>0; i--){
            if(dp[i][N]) {
                answer = i;
                break;
            }
        }
        
        cout<<answer<<endl;
        
        for(int i = 0; i<1000; i++){
            for(int j = 0; j<5001; j++){
                dp[i][j]=false;
            }
        }
    }
    
    return 0;
}