18291 비요뜨의 징검다리 건너기

처음에 문제 잘못 읽고 0부터 x만큼 건너뛰어서 n까지 도착하는 경우를 세는 줄 알았다. 

그래서 약수를 구했음ㅎㅎ..

 

i64 n;
    cin >> n;

    n--;
    i64 ans = 2;
    for (i64 i = 2; i*i < n; i++)
    {
        if (n / i == 0)
            cout << "i : " << i << endl;
    }
    cout << ans << endl;

 

다 짜고나서 4를 넣었는데 2가 나와서 그 때 잘못된 걸 깨달았다.

 

문제를 잘 읽읍시다

문제를 잘 읽읍시다

 

 

문제 어떻게 풀지 그려보다가 2의 제곱으로 하면 된다는 생각이 들었다.

 

이제 어떻게 구하느냐가 문제인데...

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


void solve()
{
    int n;
    cin >> n;

    if (n == 1 || n == 2)
    {
        cout << 1 << endl;
        return;
    }

    n -= 2;
    cout << (i64)pow(2, n) % 1000000007 << endl;

}

int     main()
{
    int t;
    cin >> t;

    solve();

    return 0;
}

 

제출은 이렇게 했다. 

 

내면서 틀릴 거 알고있었다. 계산과정에 오버플로우가 나지 않게 1000000007을 나눠줘야 하는데 pow는 나눠주지도 않고 엄청 큰 수가 되어 오버플로우 나겠지 싶었음

 

다음으로 미리 계산해놓으면 어떨까? 생각했다

미리 다 계산해놓은 다음에 테케로 들어오면 처리하는거지..

 

근데 그러려면 10^9짜리 배열이 필요하고 10^9는 1000MB니깐 메모리 초과가 일어나게 된다. 

 

메모리를 안 쓰려면 테케가 들어올 때마다 2의 제곱을 해야 하는데 그러면 최악의 경우 10^9번 계산하므로 시간초과..

 

결국 포기했는데 알고보니 2의 거듭제곱을 빠르게 logN번에 구할 수 있었다!!!

 

심지어 이전에 했었음ㅋㅋㅋㅋ ㅠㅠㅠㅋㅋ 기억합시다 기억합시다

 

---

 

거듭제곱 코드 

 

logN번 걸린다 최고!

 

#define MOD 1000000007

i64 ipow(i64 n, i64 x)
{
    if (x == 0)
        return 1;

    i64 half = ipow(n, x / 2);
    half = (half * half) % MOD;

    if (x % 2 == 0)
        return half;

    return (half * n) % MOD;
}

 

아래는 제출한 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

#define MOD 1000000007

i64 ipow(i64 n, i64 x)
{
    if (x == 0)
        return 1;

    i64 half = ipow(n, x / 2);
    half = (half * half) % MOD;

    if (x % 2 == 0)
        return half;

    return (half * n) % MOD;
}

int     main()
{
    int t;
    cin >> t;

    for (int i = 0; i < t; i++)
    {
        int n;
        cin >> n;

        cout << ipow(2, max(0, n - 2)) << endl;
    }

    return 0;
}