백준 바킹독 재귀 모음 - 1629 곱셈,

1629 곱셈

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

long long pow(long long a, long long b , long long c)
{
    //b가 홀수면 ,
    if (b == 1)
        return a%c;
    long long val = pow(a, b/2, c);
    val = val*val%c;
    if (b%2 == 0) return val;
    return val * a % c;
}
int main()
{
    long long a,b,c;
    cin>>a>>b>>c;
    cout<<pow(a,b,c);
}

난 재귀가 너무 어렵다 엉엉

 

11729번

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long cnt = 0;


void func2(int a, int b, int n)
{
    cnt++;
    if(n==1)
        return ;
    func2(a, 6-a-b, n-1);
    func2(6-a-b, b, n-1);
}

void func(int a, int b, int n)
{
    cnt++;
    if(n==1)
    {
        cout<<a<< ' '<< b<<'\n';
        return ;
    }
        
    func(a, 6-a-b, n-1);
    cout<<a<< ' ' << b << '\n';
    func(6-a-b, b, n-1);
}
int main()
{
    int n;
    cin>>n;
    func2(1,3,n);
    cout<<cnt<<'\n';
    func(1,3,n);
}

이거 횟수 구하는거는 2^k -1 인데 좀 일찍 생각했으면 저렇게 멍청하게 안하고 할 수 있다. 시간 초과나면 고치려 했는데 안뜨니 그냥 넘어갈란다ㅋㅋ

저 2^n -1 은 비트연산으로 가능하다.

(1<<n)-1

1비트씩 왼쪽으로 밀면 2제곱이 된당!