[문제풀이] 백준 1052 - 물병

📢 문제

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

📢 알고리즘

그리디

📢 풀이

#include <iostream>

using namespace std;

int N, K; //처음 물병 개수, 목표 물병 개수

int main(void)

{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> K;

  if (N <= K)
  {
    cout << 0 << "\n";
    return 0;
  }

  int plusCnt = 0; //추가구매한 물병 개수
  while (1)
  {
    int nowCnt = 0; //현재 가져갈 물병 개수
    int tempN = N + plusCnt;

    // nowCnt 구하기
    while (tempN > 0)
    {
      if (tempN % 2 == 1)
      {
        nowCnt++;
      }
      tempN = tempN / 2;
    }

    // nowCnt <= K면 답 출력
    if (nowCnt <= K)
    {
      cout << plusCnt << "\n";
      break;
    }

    // nowCnt > K면 추가구매 더 하기
    plusCnt++;
  }
}

• N=7, K=2이라고 해보자. {1, 1, 1, 1, 1, 1, 1}인 상태.
• 7/2 = 3, 7%2 = 1 이므로 2개씩 합쳐 3개의 물병이 되고, 합치지 못한 1개의 물병이 남는다.
  • {{1, 1}, {1, 1}, {1, 1}, 1}
• 합치지 못한 물병 1개는 앞으로도 그 어떤 물병과도 합칠 수 없다(물의 양이 다르기 때문)
• 따라서 nowCnt++;
• 이제 3개의 물병에 대해 똑같이 수행한다.
• 3/2 = 1, 3%2 = 1 이므로 2개씩 합쳐 1개의 물병이 되고, 합치지 못한 1개의 물병이 남는다.
  • {{2, 2}, 2}
• nowCnt++;
• 이제 1개의 물병에 대해 똑같이 수행한다.
• 1/2 = 0, 1%2 = 1 이므로 2개씩 합쳐 0개의 물병이 되고, 합치지 못한 1개의 물병이 남는다.
• nowCnt++;
• nowCnt=3이므로 nowCnt>K
• 따라서 물병을 추가구매 해야한다 : plusCnt++;
• int tempN = N + plusCnt; : 추가구매 후 새로운 총 물병 개수
• 두번째 과정부터 다시 시작!

참고자료
https://yabmoons.tistory.com/199