백준 1052번 - 물병 (C++)

문제

해결 방법

입력값을 2진수로 변환하여 string에 저장한다.(10입력 -> 1010저장 = 2^3L물병 1개, 2^1L 물병 한개라는 뜻) 이후 가장 L가 적은 물병들을 합쳐주고, 이를 string 내부의 1 갯수(물병갯수)가 내가 들 수 있는 물병의 갯수보다 같거나 작아질때까지 반복한다. 이 과정에서 L가 작은 물병들을 합치기 위해 사용한 추가 물병의 갯수 만큼 답을 출력한다.

아쉬웠던 점

예시로 1000을 탐색할 때, 역순으로 탐색하며 0을 만나면 0 갯수를 누적시켜주고 1을 만나면 누적시킨 0의 갯수만큼 특정 변수에 누적시키는 형태를 띄고 있는데, 구조상 진행하면서 해당 탐색 인덱스 뒤에 0밖에 올 수 없기 때문에 그냥 자릿수를 통해서 내 뒤에 있는 0의 갯수를 구할 수 있었다. 지금 생각났네

+지금 생각해보니까 whlie도 필요 없이 그냥 뒤에서부터 한번만 순회하는걸로 끝낼 수 있는 문제인 것 같다. 비효율적으로 짰네 ㅠ

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
 
string to_binary(int num) {
    string s = "";
    while (num > 0) {
        if (num % 2 == 1) s = "1" + s;
        else s = "0" + s;
        num >>= 1;
    }
    return s;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int a, b, L = 2, Ans = 0, INum = 0;
    cin >> a >> b;
    string Str = to_binary(a);
 
    for (auto i : Str)
        if (i == '1')
            INum++;
 
    while (INum > b)
    {
        int Zero = 0;
        for (int i = Str.size()-1; i >= 0; --i)
        {
            if (Str[i] == 0)
                Zero++;
            else
            {
                Ans += pow(2, Zero);
                while (Str[i] == '1')
                {
                    INum--;
                    Str[i] = '0';
                    i--;
                    if (i < 0)
                    {
                        Str = "0" + Str;
                        i = 0;
                    }
                }
                INum++;
                Str[i] = '1';
                break;
            }
        }
    }
 
    cout << Ans;
}

입력받은 10진수를 2진수로 변환하여 string에 저장한 후, string을 뒤에서 부터 탐색하여 1을 만나면 2^여태까지 지나온 0 갯수를 정답 출력 변수인 Ans에 누적시킨다. 이후 해당 1을 올림해주고, 연쇄올림 또한 고려하여 처리해준다. 이를 string에 내부에 있는 1(물병)의 갯수가 내가 들 수 있는 물병의 갯수보다 같거나 작아질 때 까지 반복한다.

 

잡설 : 이론상 들 수 없으면 -1을 출력하라는데 이론상 들 수 없는 경우가 없다.... 왜있는거야