Baekjoon 2629 (양팔저울)

Baekjoon 2629, 백준 2629 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <cstring>
#include <cstdlib>

#define MAX_WEIGHT 500
#define MAX_WEIGHT_NUM 30
#define MAX_WEIGHT_VAL 40000
#define MAX_TEST_NUM 7

int main() {
    // Initialization: save inputs
    int weight_num, test_num;
    int W[MAX_WEIGHT_NUM + 2], T[MAX_TEST_NUM + 2];
    scanf("%d", &weight_num);
    for(int i = 0; i < weight_num; i++){
        scanf("%d", &W[i]);
    }
    scanf("%d", &test_num);
    for(int i = 0; i < test_num; i++){
        scanf("%d", &T[i]);
    }

    // Using 2D-array for DP
    // if using 0th~ith weight can make weight j, DP[i][j] = true
    bool DP[MAX_WEIGHT_NUM+2][MAX_WEIGHT_VAL+2] = {false};
    DP[0][W[0]] = true;
    DP[0][0] = true;
    // Set values of array DP
    for(int i = 1; i < weight_num; i++) {
        for(int j = 0; j < MAX_WEIGHT_VAL; j++) {
            DP[i][j] = DP[i-1][j] or DP[i-1][std::abs(j+W[i])] or DP[i-1][std::abs(j-W[i])];
        }
    }

    for(int i = 0; i < test_num; i++) {
        if(DP[weight_num - 1][T[i]])
            printf("Y");
        else printf("N");
        if(i != test_num - 1)
            printf(" ");
    }
}

2차원 배열로 DP를 돌리는, 어찌 보면 유명한 유형의 DP(동적 계획법) 문제라고 할 수 있겠다. 문제 설명에는 ‘냅색 알고리즘’ 이라고 나와 있다.
본인은 다음의 두 가지를 고려하지 못하여 한 번씩 틀리고 세 번째 제출에 ‘맞았습니다’를 볼 수 있었다.

1. 답안 출력 형태
   여러 숫자들이 space 한 칸을 기준으로 나열되는데, for 문에서 출력 -> space 이런 식으로 하니 마지막 답안의 뒤에도 자연스럽게 space가 붙어서 나온다. 사실 이 때문에 ‘틀렸습니다’가 뜨는지는 모르겠으나, 엄밀히 따지면 문제에도 답안 사이에만 공백을 두라는 말이 있으므로 틀렸다고 해도 할 말은 없다. 이렇게 한 try를 날리면 아쉬우니까 꼭꼭 답안 출력 형태를 꼼꼼히 보자.
2. DP 초기화
   본인은 DP[0][W[0]] = true 만을 두었었는데, DP[0][0] = true 도 해 주어야 한다. (0번째 추를 사용하지 않는 경우) 명백한 실수! 실수 줄이자.