[BOJ] - Choose Your Own Arithmetic

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

BOJ - Choose Your Own Arithmetic

문제 유형: 수학, 다이나믹 프로그래밍, dfs, 재귀, 백트래킹

문제 난이도: Silver I

시간 제한: 2초

메모리 제한: 512MB

 

문제

In Waterloo, you probably have seen some geese. How can you see geese with your calculator? Start with 6, add 7, multiply by 6, multiply by 8, add 7, multiply by 8, and multiply by 7, giving 35336. Then if you flip your calculator upside down, it says gEESE:

You want to write a program to help automatically build tricks of this type. However, your calculator has a lot of broken buttons: the only mathematical operators that work are + and ×, and only a few of the digits work. Your goal is to figure out whether your half-broken calculator can achieve a given target value, using single-digit inputs and a fixed number of operations.

Note: the calculator performs the operations as soon as they are entered, rather than following any rules for order of operations (see Sample Input 2).

 

반쯤 고장난 계산기가 있는데, 특정 숫자만 입력가능하다.

연산은 곱셈 또는 덧셈만 가능하다.

특정 횟수의 연산으로 특정 목표값에 도달할 수 있는지 알아내야 한다.

 

입력

The first line of input is W, the exact number of operations you must use. W will be an integer between 0 and 6. The second line of input is 1 ≤ D ≤ 10, the number of working digit keys. On each of the D following lines, a working digit is given; these values are distinct integers from 0 to 9. Finally, an integer 1 ≤ V ≤ 5 is given, the number of target values; on each of the following V lines there is an integer between 0 and 5000000 (inclusive) giving a target value which you’d like to achieve on your calculator.

 

첫 줄에는 W가 주어집니다, 연산의 횟수입니다. 정확히 W번 연산해야 합니다. (0 <= W <= 6)

둘째 줄에는 D(1<=D<=10)이 주어집니다. 작동가능한 숫자키의 수입니다.

이후 D줄동안, 0~9사이의 값이 입력됩니다.

그 다음줄에는 정수 V(1<=V<=5)가 주어집니다. 목표 수치의 개수입니다.

이후 V줄동안 목표 수치를 받습니다. 0이상 5000000이하입니다.

 

출력

The output consists of V lines corresponding to the target values; each line contains “Y” if that target value can be achieved, and “N” if it cannot be achieved, using exactly W operations with the D given digits.

Precisely, a target value T can be achieved if, starting with one of the D digits, and then by adding or multiplying exactly W times by one of the digits, you end up with T. Digits can be re-used, and you do not need to use all of the digits. You cannot enter multi-digit numbers.

 

각 목표 수치에 대해서 가능하면 "Y", 불가능하면 "N"을 출력하시오. 정확히 W번의 연산을 해야하고, 특정 연산을 사용하지 않거나, 특정 숫자를 사용하지 않을 수 있습니다.

대신, 한 자릿수씩만 연산을 적용해야 합니다.

 

풀이

dp[테스트케이스 번호][깊이][현재 base]로 저장한다. -1은 방문안함, 1은 가능, 0은 불가능이란 뜻으로 하기로 했다.

각각에 케이스에 대해 dfs한다. 각각 모두 가능한 base부터 시작시켜서, 한 번이라도 가능한 경우가 나오면 된다. 이를 or연산을 이용했다.

각 dfs에서는, base가 target보다 커지거나 탐색 깊이가 w보다 커지면 false를 반환하도록 했고, base가 target이면서 정확히 w깊이라면, true를 반환하게 했다. 또는, dp에 방문한적이 있다면, 그 결과를 반환한다.

아니면, 각각 가능한 digits들의 +, *연산을 한 경우의 수별로 dfs호출을 시켰다.

OR연산으로 한 번이라도 가능한 경우가 발견되면, dp[times][depth][target]에 1을 아니면 0을 저장한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int w;
int d;
int v;

int digits[10];
int targets[5];

short dp[5][7][5000001];

bool dfs(int base, int target, int depth, int times) {
  if (base > target || depth > w)
    return false;
  if (base == target && depth == w)
    return true;
  if (dp[times][depth][base] != -1)
    return dp[times][depth][base] == 1;

  bool flag = false;
  for (int i = 0; i < d; ++i) {
    flag |= dfs(base + digits[i], target, depth + 1, times);
    flag |= dfs(base * digits[i], target, depth + 1, times);
    if (flag)
      break;
  }
  int res = flag ? 1 : 0;
  return dp[times][depth][base] = res;
}

void solve(int times) {
  bool ans = false;

  for (int i = 0; i < d; ++i) {
    ans |= dfs(digits[i], targets[times], 0, times);
  }

  if (ans)
    cout << "Y\n";
  else
    cout << "N\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  memset(dp, -1, sizeof(dp));

  cin >> w;
  cin >> d;

  for (int i = 0; i < d; ++i) {
    cin >> digits[i];
  }

  cin >> v;

  for (int i = 0; i < v; ++i) {
    cin >> targets[i];
  }

  for (int i = 0; i < v; ++i) {
    solve(i);
  }

  return 0;
}