16724번 원영이는 ZOAC과 영원하고 싶다

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

정말... 하루 종일 고민한 문제이다... 풀면서 비트마스크를 공부해야하나라고 생각까지 했다.

개인적으로 이 문제는 관점에 따라 접근 방식을 바로 찾고 이해하면, 쉽게 풀리는 문제라고 생각한다.

그게 아니라면, 나처럼 엄청난 시간을 소비하면서도 무식하게 구현하여 틀리게 된다.

제 1회 = 2

제 2회 = 4

제 3회 = 2

제 4회 = 8

제 5회 = 2

제 6회 = 4

제 7회 = 2

제 8회 = 16

제 9회 = 2

제 10회 = 4

제 11회 = 2

제 12회 = 8

.

.

.

제 24회 = 16

.

.

.

처음에 나는 위에처럼 나오길래 4회씩 끊어서(1~4, 5~8, ...) 생각하였다.

그래서, 2, 4, 2는 반복되니 제외해두고 4의 배수인 4회, 8회, 12회 ... 이렇게 생각하였는데 도저히 감을 잡을 수가 없었다.

특히, 제 24회는 16이 나오는 것도 그렇고, 무식하게 구현하여 제출하였지만, 당연히 시간 초과가 떴다.

그래서 도움을 받고 깨달았는데, 나는 처음부터 관점을 다르게 접근하고 있었다.

홀수일 때는 2이고, 짝수일 때는 최소가 4이다. 

2회 = 4 = 2 + 2

4회 = 8 = 2 + 2 + 4

6회 = 4 = 2 + 2

.

.

.

(참고) 24회 = 2 + 2 + 4 + 8

예를 들어, 1회 ~ 6회 합을 구하라고 했을 때,

6 / 2 = 3(6회 이하의 짝수들에서 2로 나누어 떨어지는 경우의 수 = 3개) → 3 * 2 = 6

6 / (2*2) = 1(6회 이하의 짝수들에서 4로 나누어 떨어지는 경우의 수 = 1개) → 1 * 4 = 4

위에 처럼 구현해서 전체*2를 해도 되고, 바로 아래처럼 홀, 짝 따로 계산해도 된다.

홀수, 짝수 따로 계산

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    long long N = 0, result = 0, two = 2, q = 0, cnt = 2;
 
    scanf("%lld", &N);
 
    // 홀수
    result = 2 * ( (N + 1) / 2 );
 
    // 짝수
    while (two <= N)
    {
        q = N / two;
 
        result += q * (two + cnt);
 
        cnt = 0;
 
        two *= 2;
    }
 
    printf("%lld\n", result);
 
    return 0;
}

전체에 대한 최솟값 2를 미리 더한 후 계산 시작

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    long long N = 0, result = 0, two = 2, q = 0;
 
    scanf("%lld", &N);
 
    
    result += N * 2;
 
    
    while (two <= N)
    {
        q = N / two;
 
        result += q * two;
 
        two *= 2;
    }
 
    printf("%lld\n", result);
 
    return 0;
}