14226 이모티콘

* 초안

#include<iostream>
 
using namespace std;
 
int S;
int time = 1;
 
void solve(int queue, int monitor) {
    time++;
 
    // ending 조건
    if (S == monitor)
        return;
 
    // return 조건
    if (queue == 0)
        return;
    if (monitor == 1)
        return;
 
    // C(Copy, 복사)
    solve(monitor, monitor);
 
    // P(Paste, 붙여넣기)
    solve(queue, monitor + queue);
 
    // D(Delete, 삭제)
    solve(queue, monitor - 1);
}
int main() {
    cin >> S;
 
    solve(0, 1);
    
    cout << time;
 
    return 0;
}

당연히 안될거라 생각했는데, 왜 안되는진 모르겟당..

* 가지 3개 만들어서 재귀, 백트래킹이 되어버렸넹? BFS짤라했는데..!

#include<iostream>
 
using namespace std;
 
int S;
int time = 0;
 
 
void solve(int queue, int monitor, int copyCnt) {
    time++;
 
    // ending 조건
    if (S == monitor)
        return;
 
    // return 조건
    if (queue == 0)
        return;
    if (monitor == 0)
        return;
    
    if (copyCnt >= 2) {
        return;
    }
 
    // C(Copy, 복사)
    solve(monitor, monitor, copyCnt + 1);
    time--;
 
    // P(Paste, 붙여넣기)
    solve(queue, monitor + queue, 0);
    time--;
 
    // D(Delete, 삭제)
    solve(queue, monitor - 1, 0);
    time--;
 
}
int main() {
    cin >> S;
 
    // C
 
    solve(1, 1, 1);
 
    // P
    solve(0, 1, 0);
 
    // D
    solve(0, 0, 0);
    
    cout << time;
 
    return 0;
}