BOJ 1052 - 물병

boj

• 이진수를 떠올려 보는게 포인트 였다. (팀원들의 리뷰와 이해를 도와주신 로니님 감사👍)

  • 10진수	2진수	홀수
    1	01	✔️
    2	10	-
    3	11	✔️
    4	100	-
    5	101	✔️

• 십진수 15의 2진수

  • 1	1	1	1
    8의 자리	4의 자리	2의 자리	1의 자리

• 이진수 1의 자리가 1 일 때만 물병 추가로 2의 자리가 1이 되면 동등한 양으로 물병을 채울수 있게 된다.

• 그러면, 주어진 n개의 값에서 물병 1개씩 추가하면서 k개는 어떻게 맞출까?

  • 2개의 물병이 1개로 준다.

    • 2L 물병1개 + 2L 물병1개 = 4
      0010 + 0010 = 0100
      1의 개수 : 2개 → 1개

  • 예제 n = 13, k=2

    • 처음 1L + 1L → 2L → 4L → 8L
      • 복잡하니 4L까지 합쳤을 때, 추가 전 14L의 이진수 1110
        • 0100 + 0100 + 0100 + 0010 = 1110
        • 1Lx2개 추가하면 16L = 0001 0000
    • 13에서 물병 1개씩 추가
      • 13 → 14 (1110) +1
      • 14 → 15 (1111) +1
      • 15 → 16 (0001 0000) +1
  
  

• 이해한 선에서 코드 표현

	@ParameterizedTest
	@MethodSource("providerParam")
	void test(int n, int k, int expect) {
		long count = 0L;
		long buy = 0L;

		while (true) {
			String binary = Integer.toBinaryString(n);
			count = binary.chars()
				.filter(value -> value == 1+'0')
				.count();

			if (count <= k) {
				break;
			}
			n++;
			buy++;
		}

		if (count > k) {
			buy = -1;
		}

		assertEquals(buy, expect);
	}