[BOJ] 재귀

바로 시작해보겠습니다.

 

[BOJ 10872]

 

switch-case문으로 구현해주었습니다.

#include <stdio.h>

unsigned int fact(unsigned int N){
    switch(N){
        case 0:
        case 1:
            return 1;
        default:
            return fact(N-1) * N;
    }
}

int main(){
    int N;
    scanf("%d",&N);
    printf("%d", fact(N));
}

 

[BOJ 10870]

 

switch-case문으로 구현해주었습니다. 2

#include <stdio.h>

unsigned fibb(unsigned N){
    switch(N){
        case 0:
            return 0;
        case 1:
        case 2:
            return 1;
        default:
            return fibb(N-1) + fibb(N-2);
    }
}

int main(){
    int N;
    scanf("%d",&N);
    printf("%d",fibb(N));
}

 

[BOJ 2447]

 

문자열 버퍼를 만들어놓고 재귀적으로 저장하는 방식으로 구현해주었습니다.

#include <stdio.h>
#include <vector>
#include <string>

using namespace std;

class star10{
    public:
    vector<string> starbuf;
    star10(int N) : starbuf(N, string(N, ' ')){
        drawstar(N, 0, 0);
    }
    void printstar(){
        for(int k=0;k<starbuf.size();++k)
            printf("%s\n",starbuf[k].c_str());
    }
    private:
    int drawstar(int N, int x, int y){
        if(N == 1){
            starbuf[y][x] = '*';
        } else{
            N /= 3;
            drawstar(N, x+0,    y+0);
            drawstar(N, x+N,    y+0);
            drawstar(N, x+2*N,  y+0);
            drawstar(N, x+0,    y+N);
            drawstar(N, x+2*N,  y+N);
            drawstar(N, x+0,    y+2*N);
            drawstar(N, x+N,    y+2*N);
            drawstar(N, x+2*N,  y+2*N);
        }
        
        return 0;
    }
};

int main(){
    int N;
    scanf("%d",&N);
    star10 P(N);
    P.printstar();
}

 

[BOJ 11729]

 

재귀적으로 구현해주되 출발과 도착이 있고 남은 봉 하나도 함수 인자로 주어서 사용할 수 있게끔 하면 되겠습니다.

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

using namespace std;

class hanoitower{
    public:
    int N;
    int K;
    typedef pair<int, int> move_t;
    vector<move_t> proc;
    hanoitower(int N){
        this->N = N;
        this->K = performhanoi(N, 1, 3, 2);
    }
    int printhanoi(){
        for(const move_t & s : proc)
            printf("%d %d\n", s.first, s.second);
        return 0;
    }
    private:
    int performhanoi(int N, int from, int to, int aux){
        switch(N){
            case 0:
                return 0;
            case 1:
                {
                    proc.push_back({from, to});
                    return 1;
                }
            default:
                {
                    int movecount = 0;
                    movecount += performhanoi(N-1, from, aux, to);
                    proc.push_back({from, to});
                    movecount++;
                    movecount += performhanoi(N-1, aux, to, from);
                    return movecount;
                }
        }
        return -1;
    }
};

int main(){
    int N;
    scanf("%d",&N);
    
    hanoitower H(N);
    printf("%d\n", H.K);
    H.printhanoi();
}

 

감사합니다.