백준 4417, 9305 - Yahtzee

https://www.acmicpc.net/problem/9305
https://www.acmicpc.net/problem/4417

먼저 9305번, 최적 조합의 해를 구하는 문제다.

13개의 주사위 조합을 13개의 족보(category)에 넣어 최고점을 출력하기만 하면 되는 문제이다.

처음 생각은 dp[족보][주사위 조합][사용된 주사위 조합의 비트마스킹] 인
dp[13][13][1 << 13] 을 활용해 bitmasking + dp로 풀어내려고 했으나, 메모리도 시간도 조건과 안맞았다.

문제를 더 이해해보면 모든 족보를 전부 한 번씩, 모든 주사위 조합을 사용해야 하는 문제이기때문에

dp[족보][사용된 주사위 조합의 비트마스킹] 만으로도 모든 경우를 계산할 수 있었다.

Ones에 0~12번 조합을 전부 넣어보고 ... dp[0][visited | (1 << i)]

Twos에 비트마스킹으로 방문하지 않은 모든 조합을 전부 넣어보고 ... dp[1][visited | (1 << i)]

총 dp[12][1 << 13]의 캐시에 모든 정보를 담을 수 있었다.

보너스 계산을 위해 방문하는 족보의 순서를 top-down의 역으로 바꾸었다. (Yahtzee -> FullHouse -> ... )

#include <iostream>
#include <algorithm>
using namespace std;

int c[13][5];
int dp[13][8192];
int Nums(int x[], int n){
  int point = 0;

  for(int i = 0; i < 5; i++){
    if(x[i] == n) point += n;
  }

  return point;
}

int Chance(int x[]){
  return x[0] + x[1] + x[2] + x[3] + x[4];
}

int ToK(int x[]){
  if((x[0] == x[2]) || (x[1] == x[3]) || (x[2] == x[4])){
    return x[0] + x[1] + x[2] + x[3] + x[4];
  }
  return 0;
}

int FoK(int x[]){
  if((x[0] == x[3]) || (x[1] == x[4])){
    return x[0] + x[1] + x[2] + x[3] + x[4];
  }
  return 0;
}

int SS(int x[]){
  int temp[7] = {0, 0, 0, 0, 0, 0, 0};
  for(int i = 0; i < 5; i++){
    temp[x[i]]++;
  }
  if(temp[1] && temp[2] && temp[3] && temp[4]) return 25;
  if(temp[2] && temp[3] && temp[4] && temp[5]) return 25;
  if(temp[3] && temp[4] && temp[5] && temp[6]) return 25;
  return 0;
}

int LS(int x[]){
  for(int i = 0; i < 4; i++){
    if(x[i] != x[i+1] - 1){
      return 0;
    }
  }
  return 35;
}

int FH(int x[]){
  if(x[0] == x[1] && x[2] == x[4]) return 40;
  if(x[0] == x[2] && x[3] == x[4]) return 40;
  return 0;
}

int Yahtzee(int x[]){
  if(x[0] == x[4]){
    return 50;
  }
  else return 0;
}


int getPoint(int x[], int category){
  if(category < 6){
    return Nums(x, category + 1);
  }
  if(category == 6){
    return Chance(x);
  }
  if(category == 7){
    return ToK(x);
  }
  if(category == 8){
    return FoK(x);
  }
  if(category == 9){
    return SS(x);
  }
  if(category == 10){
    return LS(x);
  }
  if(category == 11){
    return FH(x);
  }
  else return Yahtzee(x);
}

int getMax(int category, int visited){
  if(category < 0) return 0;
  int &ret = dp[category][visited];
  if(ret != -1) return ret;
  ret = 0;
  for(int i = 0; i < 13; i++){
    if(visited & (1 << i)) continue;
    ret = max(ret, getMax(category - 1, visited | (1 << i)) + getPoint(c[i], category));
  }
  if(category == 5 && ret >= 63) ret += 35;
  return ret;
}

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  int T;
  cin >> T;

  for(int t = 0; t < T; t++){
    for(int i = 0; i < 13; i++){
      fill(dp[i], dp[i] + 8192, -1);
    }

    for(int i = 0; i < 13; i++){
      for(int j = 0; j < 5; j++){
        cin >> c[i][j];
      }
    }
    for(int i = 0; i < 13; i++){
      sort(c[i], c[i] + 5);
    }
    int ans = 0;
    cout << "Case " << t + 1  <<": " << getMax(12, 0) << "\n";
  }
}

출력이 "Case i: ans" 형태라는 점에 유의하자. 이거 몰라서 몇시간을..

---

다음은 4417번, 조합의 최고값과 해당 최고값을 만드는 데 사용된 점수들을 전부 추적해야하는 문제이다.

dp와 같은 크기의 track배열을 만들어서 dp의 지점별 최고값이 갱신될 때마다
track이 해당 비트마스크를 기억하도록 구현하였다.

int getMax(int category, int visited){
  if(category < 0) return 0;
  int &ret = dp[category][visited];
  if(ret != -1) return ret;
  ret = 0;
  for(int i = 0; i < 13; i++){
    if(visited & (1 << i)) continue;
    int ans = getMax(category - 1, visited | (1 << i)) + getPoint(c[i], category);
    if(ret < ans){
      ret = ans;
      track[category][visited] = (visited | (1 << i));
    }
  }
  if(category == 5 && ret >= 63) ret += 35;
  return ret;
}

visited를 기억하면, dp[category][visited]로 그때의 점수에 쉽게 접근할 수 있다.

    //....
    int ans = getMax(12, 0);
    
    int bef = 0;
    stack<int> history;
    history.push(dp[12][0]);
    for(int i = 12; i > 0; i--){
      bef = track[i][bef];
      history.push(dp[i - 1][bef]);
    }

    int s = 0;
    int bonus = 0;
    for(int i = 0; i < 6; i++){
      int temp = history.top();
      bonus += temp - s;
      if(i == 5 && bonus >= 63) cout << temp - s - 35 << " ";
      else cout << temp - s << " ";
      s = temp;
      history.pop();
    }

    for(int i = 0; i < 7; i++){
      int temp = history.top();
      cout << temp - s << " ";
      s = temp;
      history.pop();
    }

    cout << (bonus >= 63 ? 35 : 0) << " ";
    cout << ans << "\n";

아, 이 문제는 Yahtzee의 족보가 마지막이 아니고 Four of King 다음이라는 점도 유의해야 한다.

영차영차 알고리즘도 하는중...ㅎ