백준 16723번 원영이는 ZOAC와 영원하고 싶다

문제 링크입니다: https://www.acmicpc.net/problem/16723

N의 최대 범위가 1,000,000,000 즉, 10억이기 때문에 완전탐색법으로 접근하면 TLE가 발생하는 문제였습니다.

그래서 참가자들을 다 나열해보고 규칙을 찾아보도록 하겠습니다.

$$2 + 4 + 6 + 8 + 10 + 12 + 14 + ... + 2 * N$$

$$2 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N) $$

$$2 * (1 + 3 + 5 + 7 + ... + 2 * (1 + 2 + 3 + 4 + 5+...))$$

$$2 * (1 + 3 + 5 + 7 + ... + 2 * (1 + 3 + 5 + ... + 2*(1 + 2 + 3 + ...)))$$

이로써 규칙을 찾았고 반복문을 이용해서 적절히 시간복잡도를 줄이면 AC를 받을 수 있는 문제였습니다.

#include <iostream>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        long long result = 2 * N;

        N /= 2;

        for (int i = 1; ; i++)

        {

                 //1LL 중요

                 result += (1 << i) * N * 1LL;

                 N /= 2;

                 if (N == 0)

                         break;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~