[AtCoder] AtCoder Beginner Contest 337 E - Bad Juice C++ 풀이

[문제 링크]
https://atcoder.jp/contests/abc337

[설명]

인터랙티브로 1 ~ N까지의 주스가 들어있는 병 중 상한 주스가 들어있는 병을 찾는 문제이다. 이때 M명의 친구를 동원해서 필요한 주스들을 마시게 한 후 그 결과를 통해 답을 찾아야 하며 이때의 M은 최소여야 한다. 결과는 0과 1로 이루어진 문자열로 제공된다.

결과가 0, 1로 이루어져있기 때문에 이진수를 생각해볼 수 있다. 즉, 상한 주스는 1 ~ N까지 N개의 경우가 존재하고 이 주스들을 이진수로 표현해보자. 이때, 각 주스의 번호에 1을 뺀 값을 써야 한다. N = 3일 때, 1 : 00, 2 : 01, 3 : 10이다. 2자리만으로 1이 상했을 때, 2가 상했을 때, 3이 상했을 때를 모두 나타낼 수 있다. 즉, N = 3인 경우 필요한 최소 사람의 수는 2명이다. 이를 N으로 나타내면 M = ⌈$log_{2}N$⌉임을 알 수 있다.

따라서 각 주스의 번호에서 1을 뺀 값을 이진수로 나타낸 후 1이 등장한 위치에 해당하는 사람에게 그 주스를 준다고 한다면 최소인 M으로 답을 찾을 수 있다.

[코드]

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

int n, m;
string s;
vector<int> tmp;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int i, j, k, ans = 0; cin >> n;
    double t = log2(n);
    if ((double)((int)t) != t) m = (int)t + 1;
    else m = (int)t;
    cout << m << endl;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            k = (j >> i);
            if ((k & 1) == 1) tmp.push_back(j + 1);
        }
        cout << tmp.size() << ' ';
        for (auto& iter : tmp) cout << iter << ' ';
        cout << endl;
        tmp.clear();
    }
    cin >> s;
    i = 1;
    for(auto& iter : s) {
        if (iter == '1') ans += i;
        i *= 2;
    }
    cout << ans + 1 << endl;
}