A - 高橋君とお肉

コメント歓迎です。
今回もビット全探索を使います。

問題

AtCoder 版！蟻本 (初級編) - Qiita より

beta.atcoder.jp

方針

この問題ではお肉を肉焼き器Aと肉焼き器Bに振り分けて焼きます。
振り分けパターンのうち最短時間を求めて出力します。

肉焼き器が2台なので、それぞれのお肉をAとBどちらで焼くか考えます。
AかBの2つのうちどちらを選ぶかを考えればよいのでビット全探索が使えます。

例えばお肉が3枚だった場合はで8パターンとなります。

複数のお肉を片方の肉焼き器で焼くのは確実に最適パターンではありません。
しかし、今回はお肉が最大4枚で計算量が多くないのでそのまま計算してしまっています。

コード(AC)

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

int main(){
  // 入力
  int N;
  cin >> N;

  vector<int> time(4, 0); // 要素{0, 0, 0, 0}
  for (int i = 0; i < N; i++) {
    cin >> time[i];
  }

  int A; // 肉焼き器Aの焼き時間
  int B; // 肉焼き器Bの焼き時間
  int ans = 201;

  // ビット全探索　ビットパターン 2^N
  for (int i = 0; i < (1 << N); i++) {
    // 焼き時間初期化
    A = 0;
    B = 0;
    // "1":肉焼き器A
    // "2":肉焼き器B
    for (int j = 0; j < N; j++) {
      if (i >> j & 1) A += time[j];
      else            B += time[j];
    }
    // 短時間だったら答えに代入
    if (ans > max(A, B)) {
      ans = max(A, B);
    }
  }
  // 出力
  cout << ans << endl;
}