백준 1094번: 막대기

1. 문제

2.예제

문제의 조건은 뭔가 까다로워 보인다.

예제를 보자.

예제 1: 입력 23

[반복1]
1. 64를 절반으로 자르면 32, 32가 된다.
2. 32는 x(23)보다 크기 때문에 자른 32를 버린다.
(길이 : 32)

[반복2]
1. 32를 절반으로 자르면 16, 16이 된다.
2. 16는 x(23)보다 작기 때문에 자른 16을 버릴 수 없다.
(길이 : 16, 16)

[반복3]
1. 16을 절반으로 자르면 8, 8이 된다.
2. 24(16+8)은 x(23)보다 크기 때문에 자른 8을 버린다.
(길이 : 16, 8)

[반복4]
1. 8을 절반으로 자르면 4,4가 된다.
2. 20(16+4)은 x(23)보다 작기 때문에 자른 4를 버릴 수 없다.
(길이 : 16, 4, 4)

[반복5]
1. 4를 절반으로 자르면 2,2가 된다.
2. 22(16+4+2)는 x(23)보다 작기 때문에 자른 2를 버릴 수 없다.
(길이 : 16, 4, 2, 2)

[반복6]
1. 2를 절반으로 자르면 1,1이 된다.
2. 23(16+4+2+1)은 x(23)과 같기 때문에 자른 1을 버린다.
(길이 : 16, 4, 2, 1)

자른 길이의 총합이 23이 되었기 때문에 연산은 끝나고 막대의 총 개수인 4가 정답이 된다.

3.해제

문제를 푸는 과정은 위와 같이 길지만, 결론적으로 각 단계에서 만들어지는 막대를 사용할지, 말지를 이진수로 표현하면 된다.

즉 입력값을 2진수로 만든후, 1의 개수를 새면 되는 것이다.

따라서 입력값을 2로 나눠가며, 나머지가 1인 경우를 체크한다.

#include <iostream>
using namespace std;

int main()
{
    int n, ans = 0;
    cin >> n;

    n *= 2;
    while (n /= 2)
    {
        if (n % 2 == 1)
            ans++;
    }

    cout << ans << endl;
}