[11주차_수요일] 물병

[yeongleej]

• 사이트 : 백준(BOJ)
• 문제: 물병
• 번호: 1052

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[baexxbin]

🤔 시간복잡도 고려사항

• N <= 10^7
• K <= 1,000
• 완전탐색 불가

💡 풀이 아이디어

• 처음 아이디어
  • 만들어야할 묶음 수 구하기(t): 2*K
  • N/t 후 나머지가 생기면 물병이 더 필요한 것으로 (t*나머지)에 따라 필요한 물병 수 구하기

    이 방법은 t가 2의제곱꼴일 경우만 사용 가능 (예시 3처럼 K가 2배수 아니면 사용 불가) → 2의제곱 형태를 더 활용하기

• 비트 활용
  • N을 이진수, 즉 비트형태로 표현했을때 각 자리의 1은 2의 제곱꼴에 해당
    • 1은 뭉쳐진 물병을 나타내고, 1의 개수는 총 뭉쳐진 물병의 수를 나타냄
  • 1의 개수가 K개가 될때까지 물병 추가해나가기
    • 이때 물병추가는 가장 낮은 자리의 비트부터 추가하기
    • 추가된 값이 곧 추가한 물병의 수
  • 비트 연산
    • Integer.bitCount(N) : 현재 숫자의 비트에서 1의 수 구하기
      • 해당 함수의 시간복잡도는 O(logN)
    • int lowPos = N & -N; : 가장 낮은 자리 비트 구하기
      • -N은 N을 보수연산한 것으로 가장 낮은 자리 번호를 제외하고 0과 1뒤바뀜.
      • 해당 특징을 이용해 기존 N과 &연산을 해 가장 낮은 자리비트 구함

[Jewan1120]

🤔 시간복잡도 고려사항

• 수학 추론 문제라서 고려하지 않음

💡 풀이 아이디어

• 2^x + 2^y + ... 의 항의 개수가 k개 이하여야 합쳐서 옮기는 것이 가능
• 따라서 비트 연산으로 1의 비트가 k개 이하가 되도록 연산
• 최소의 물병을 더해야 하므로 최소 비트를 더해줌
  • Integer.bitCount(n): n이 갖는 1의비트 수
  • Integer.lowestOneBit(n): n의 마지막 1의 비트의 값

    while (Integer.bitCount(n) > k) {
    // 최소한의 수를 더하여 비트 줄이기
    cnt += Integer.lowestOneBit(n);
    n += Integer.lowestOneBit(n);
    }

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 10,000,000
• K <= 1,000

=> O(N)으로 생각해보기

💡 풀이 아이디어

• N의 값은 (2^0, 2^1, ....들의 합)이 되어야 함

• K >= N이라면 한번에 모든 물병 들 수 있으므로 0

• 내가 푼 과정

1. K-1개의 물병 담기
   • N에서 2^i을 계속 빼줘서 물병 사용하기
   • 2^i는 N보다 작은 최대 2의 제곱수
   • 이떄 N이 0이되면 0 출력
2. 1번에서 N이 0이 되지 않았다면, 마지막 물병을 만들기 위한 구매해야 하는 최소 물병 개수 구하기
   • 2^i > N인 값 구하기
   • 2^i - N == N이 2^i가 되기 위해 구매햐야 하는 물병 수

• 비트마스킹 활용하기
• N은 (2^0, 2^1, ....들의 합)이 되어야 한다
  • 즉, N을 2진수로 표현했을 때, 1의 개수가 K가 되야 함
• Integer.bitCount(N) : N(10)을 2진수로 나타낸 후 1의 개수

• N의 2진수에서 1의 개수를 카운트
  • 개수가 K보다 작거나 같다면 stop
• 개수가 K보다 크다면, N++, 필요한 물병수++

int ans = 0; while(true) { int bc = Integer.bitCount(N); if(bc <= K) break;

N++;
ans++;

}

> 비트연산 쉽지않네요 ㅜㅜㅠㅠ 😢 

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 그리디
• 시간복잡도: N은 10^7 K는 10^3 으로 최대 O(N) 이내로 풀이가능

💡 풀이 아이디어

• 기본 물의 양은 1, 물 2개를 계속해서 합치면 2의 제곱이 됨
• N보다 작은 2의 최대 제곱 수가 합친 최대 물의 양 으로 1개의 물병을 만들 수가 있음
  • K-1 개 만큼 반복하면서 물병을 만들고, 물병이 0이 된다면 K개 이내로 물병을 만들 수 있다는 뜻으로 반복문을 탈출한다. (상점에서 물병을 살 필요가 없으므로 -1 출력)

    for(int i=0; i<K-1; i++){
    int count = 0;
    while(Math.pow(2,count) < N){  //N개의 물병을 넘지 않는 최대 제곱
     count++;
    }
    N -= (int) Math.pow(2,count-1);   //물병 1개를 만들 수 있는 최대양
    if(N == 0) {
     break;
    }
    }

• K-1 개 반복 후 N 이 남아있다면 상점에서 물병을 사서 보충하기
  • Math.pow(2,count) < N 2의 제곱만큼 순회를 통해 N 보다 작은 최대 물의 양의 제곱(count)을 구한 후,
  • (int) Math.pow(2,count) - N 출력

그런데 10 3 를 입력하면 0 으로 출력 되던데, 정답으로 넘어가더라구요? 0개는 -1 로 출력해야 하는것 아닌가요..??? (그런데 0일 경우 -1 로 변환해서 출력하게 하면 오답으로 돼요)