[2629번] 양팔저울

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

이 문제는 결국 현재무게, 현재무게에서 다음 추를 더한 무게, 현재무게에서 다음 추를 뺀 무게(절댓값)을 이용하면 된다.

이때 dp로 변경시키기위해 dp를 다음과 같이 정의한다.

dp[i][weight] :: i번째에서 weight를 가지는가?

이제 이를 dp로 구현해보자.

void dfs(int i, int weight)

{

if (i > n)

return;

if (dp[i][weight] != -1)

return;

dp[i][weight] = 1;

dfs(i + 1, abs(weight - arr[i]));

dfs(i + 1, weight);

dfs(i + 1, weight + arr[i]);

}

i > n일때는 종료시점이니 return을 걸어주고, dp != -1일때는 dp값이 존재하는 메모이제이션 과정이다.

그 외에는 위에서 설명한 내용과 같다.

소스 코드 : 

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 45 46 47 48 49 50 51 52 53 54 55

#include <iostream> #include <cstdio> #include <cmath> #include <memory.h> using namespace std;   int arr[32]; int dp[31][31 * 500 + 2]; int chk[10];   int n; void dfs(int i, int weight) {     if (i > n)         return;     if (dp[i][weight] != -1)         return;       dp[i][weight] = 1;       dfs(i + 1, abs(weight - arr[i]));     dfs(i + 1, weight);     dfs(i + 1, weight + arr[i]); }   int main() {     scanf("%d", &n);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       memset(dp, -1, sizeof(dp));       dfs(0, 0);       int m;     scanf("%d", &m);       for (int i = 0; i < m; i++)     {         scanf("%d", &chk[i]);         if (chk[i] > 15000)             printf("N ");         else if (dp[n][chk[i]] == 1)             printf("Y ");         else             printf("N ");     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus