[코딩테스트] 수학적 귀납법 (분할과 정복)

Algorithm

[코딩테스트] 수학적 귀납법 (분할과 정복)

쿠뱃봉 2023. 10. 23. 10:50

1. 수학적 귀납법

문제) 임의의 정수 n을 입력받아 1부터 n까지 합을 구하는 프로그램

내 풀이)

#include<iostream>
using namespace std;
int function(int n,int sum){
    if(n==0)
        return sum;
    sum+=n;
    return function(n-1,sum);
    
}

int main(){
    int n,result,sum;
    cin>>n;
    result=function(n,sum);
    cout<<result;
    
}

모범답안)

#include<iostream>
using namespace std;
int function(int n){
    if(n==1)
        return 1;
  
    return n + function(n-1);
    
}

int main(){
    int n,result;
    cin>>n;
    result=function(n);
    cout<<result;
    
}

2. 수학적 귀납법을 이용해서 k진법으로 출력하는 문제

문제) 임의의 10진법 정수 n을 입력받아 이를 k진법으로 출력하는 프로그램

내 풀이)

#include<iostream>
#include <stack>
using namespace std;
stack<int> s;
int function(int n,int k){
    if(n<k){
        s.push(n);
        return 0;
    }
    s.push(n%k);    
    return function(n/k,k);
    
}

int main(){
    int n,k,result;
    cin>>n>>k;
    function(n,k);
    while(!s.empty()){
        cout<<s.top();
        s.pop();
    }
    
    
}

아이디어)

3. 타일 채우기

문제) 2*1 혹은 2*2크기의 타일을 2*n 크기의 직사각형모양 틀에 넣으려고 한다. 이 때 가능한 경우의 수를 구하여라.

내 풀이)

#include<iostream>
#include <stack>
using namespace std;
int function(int n){
    if(n==1)
        return 1;
    if(n==2)
        return 3;
        
    return function(n-1)+function(n-2)*2;
    
}

int main(){
   int n,result,k;

   cin>>n>>k;
   
   cout<<function(n)%k;
   
    
}

아이디어)