백준 10564번 - 팔굽혀펴기

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

10564번: 팔굽혀펴기

1년전쯤 한창 DP문제를 풀며 자신감에 차 있을때 풀다가 벽을 느끼며 포기했던 문제였다.

이제는 풀 수 있을것 같아서 도전해 봤는데, 쉽진 않지만 생각하는 대로 문제가 풀리니 뿌듯했다.

 

 

필요한 배경지식

• 다이나믹 프로그래밍
• BFS

 

문제 해결 방법

배낭문제(Knapsack Problem) 풀듯이 문제를 해결했다.

득점의 종류를 이용하여 나올 수 있는 총 팔굽혀펴기의 수를 탐색하는 방법이다.

 

bool dp[i][j] : 총 i점일때 j번 팔굽혀펴기가 가능한가 ?

같은 i점이라도 나올 수 있는 총 팔굽혀펴기수가 다르기 때문에 위와 같이 dp배열을 정의했으며 탐색하는 과정에서

(i,j)쌍이 중복체크 될 수 있다고 생각해서 BFS를 이용했다.

 

전체코드

#include<bits/stdc++.h>
using namespace std;
using tpi = tuple<int,int,int>;

int T,N,M;
int m[11]{};
bool dp[555][5555]{}; // dp[i][j]: 총 i점일때 j번 팔굽혀펴기가 가능한가 ?

int solve() {
    memset(dp, 0, sizeof(dp));
    queue<tpi> q;
    for(int i=0; i<M; i++) {
        int now = m[i];
        q.push({now, now, now});
        dp[now][now] = true;
    }

    while(!q.empty()){
    	// csc: 득점한 총 점수
        // cas: 마지막으로 더한 팔굽혀펴기 수
        // cps: 총 팔굽혀펴기 수
        int csc, cas, cps; 
        tie(csc, cas, cps) = q.front();
        q.pop();

        for(int i=0; i<M; i++){
            int nsc = csc + m[i];
            int nas = cas + m[i];
            int nps = cps + nas;
            if(nps > N || dp[nsc][nps]) continue;
            q.push({nsc, nas, nps});
            dp[nsc][nps] = true;
        }
    }

    for(int i=554; i>=1; i--) {
        if(dp[i][N]) return i;
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>N>>M;
        for(int i=0; i<M; i++) cin>>m[i];
        cout<<solve()<<'\n';
    }
}