백준 14226번 : 이모 티콘

문제링크 :https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 문제설명 

 

1. 현재 화면에는 이모티콘 1개가 있다.

2. 주어진 3가지 연산을 이용하여 N개의 이모티콘을 만들려고 하는데 ,

3. 이모티콘을 만들기 위한 최소 연산 횟수를 출력 하시오. 

 

 알고리즘 

 

1. 재귀 함수를 이용하여 3가지 연산을 수행 하고 최소값을 갱신 해주었다.

 

 코드 

 

 
#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
 
int arr[2000];
 
void func(int n, int cnt, int copy) {
 
 
    //최솟값 갱신
    if (arr[n] > cnt || arr[n] == 0)
        arr[n] = cnt;
    else
        return;
 
    //1빼기
    if (n > 1 )
        func(n - 1, cnt + 1, copy);
 
 
    //붙여넣기
    if (n + copy < 2000 && copy > 0 )
        func(n + copy, cnt + 1, copy);
 
 
    //모두 복사해서 붙여넣기
    if (n + n < 2000 && n > 0 )
        func(n + n, cnt + 2, n);
 
}
 
 
 
int main() {
    cin >> N;
    arr[1] = 1;
    func(2, 2, 1);
    cout << arr[N];
 
}