https://www.acmicpc.net/problem/7569

이 문제는 BFS문제 중에서는 기초적인 문제이지만 조금 더러운 문제중 하나이기도하다.

그 이유는 이 문제에서는 여러가지 해결법이 다 통하는 문제는 아니기 때문이다.

이 문제의 의도는 "정석 BFS로 풀어라!"라는 문제이다.

그 이유는 풀면서 설명하겠다.

가로 M, 세로 N, 높이는 H이다.

그리고 하나의 토마토가 익게되면 주위의 토마토도 같이 익게된다.

이 때 익은 토마토는 1, 안 익은 토마토는 0, 토마토가 없는 칸은 -1이 된다.

이 문제는 DFS와 BFS모두 접근은 가능한데 실제로는 DFS로는 거의 못푸는 문제이다.

그 이유는 DFS로 풀게되면 엄청나게 반복을 하기 때문이다.

즉 시간을 미친듯이 잡아먹는다. 그래서 BFS로 푸는것이 좋다.

첫 예제로 보도록하자.

1)
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

2)
0 -1 0 1 1
-1 -1 1 1 1
0 0 1 1 1

3)
0 -1 1 1 1
-1 -1 1 1 1
0 1 1 1 1

4)
0 -1 1 1 1
-1 -1 1 1 1
1 1 1 1 1

실패

첫 예제를 보면 0이 결국 하나 남기 때문에 모두 익히지 못한다.

그래서 -1이 출력된다.

두번 째예제를 보자.

1)
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

2)
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
-
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0

3)
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
-
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0

4)
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0
-
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

5)
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
-
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

4번만에 성공

두번째는 총 4번만에 성공하게된다.

BFS로만 구현하면 되므로 난이도 자체는 높지는 않다.

문제는 BFS를 아느냐 모르느냐겠지만.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

ostream &operator<<(ostream &o, Point p) {
    o << "m:" << p.m << ", n:" << p.n << ", h:" << p.h;
    return o;
}

int M, N, H;
vector<vector<vector<int>>> map;
queue<Point> q;
int tmp;
Point tp;
int result = 1;
int remain = 0;
bool sw;

void print() {
    for (int h = 1; h <= H; h++) {
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                cout << map[m][n][h] << " ";
            }
            cout << endl;
        }
    }
}

int main() {
    //init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

    //logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

    //output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

코드를 보면 간단하다.

여기서 디버깅용 로직들을 제외하면 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

int M, N, H;
vector<vector<vector<int>>> map;
queue<Point> q;
int tmp;
Point tp;
int result = 1;
int remain = 0;
bool sw;

int main() {
    //init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

    //logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

    //output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

그럼 설명을 시작하겠다.

class Point {
public:
    int m;
    int n;
    int h;

    Point(int m, int n, int h) : m(m), n(n), h(h) {}

    Point() : m(0), n(0), h(0) {}
};

먼저 큐에 좌표의 정보를 담아야하니까 클래스를 만들어준다.

물론 클래스를 만들지 않아도 되지만 개인적으론 안만드는게 더 힘들 거 같다.

//init
    {
        cin >> M >> N >> H;
        map.resize(M + 1, vector<vector<int>>(N + 1, vector<int>(H + 1, 0)));
        for (int h = 1; h <= H; h++) {
            for (int n = 1; n <= N; n++) {
                for (int m = 1; m <= M; m++) {
                    cin >> tmp;
                    map[m][n][h] = tmp;
                    if (tmp == 1) {
                        q.push(Point(m, n, h));
                    } else if (tmp == 0) {
                        remain++;
                    }
                }
            }
        }
    }

초기화 로직도 중요한데

다른게 아니라 바로 remain이라는 변수의 존재이다.

우리는 성공했을 때와 실패했을 때를 구별해야한다.

즉 모든 BFS를 돌았을 때 0이 남지 않아야한다.

0이 남으면 실패한것인데 이걸 해결할 수 있는 방법은 2가지가 있다.

하나는 이렇게 미리 0의 갯수를 새고 익은녀석마다 0의 갯수를 지우는 것,

또다른 것은 BFS가 끝나고 마지막에 0의 갯수를 새는 것이다.

물론 시간복잡도는 똑같으니 뭘해도 상관없지만 깔끔하게 하고싶다면 위 방법을 추천한다.

bool chkAll() {
    bool result = true;
    for (int h = 1; h <= H; h++) {
        for (int n = 1; n <= N; n++) {
            for (int m = 1; m <= M; m++) {
                if (map[m][n][h] == 0) {
                    result = false;
                }
            }
        }
    }
    return result;
}

만약 마지막에 0의 갯수를 새고 싶다면 위처럼 사용해주면 된다.

//logic
    {
        while (!q.empty()) {
            tp = q.front();
            q.pop();
            sw = false;
            if (0 < tp.m - 1 && map[tp.m - 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m - 1, tp.n, tp.h));
                map[tp.m - 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.m + 1 <= M && map[tp.m + 1][tp.n][tp.h] == 0) {
                q.push(Point(tp.m + 1, tp.n, tp.h));
                map[tp.m + 1][tp.n][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.n - 1 && map[tp.m][tp.n - 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n - 1, tp.h));
                map[tp.m][tp.n - 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.n + 1 <= N && map[tp.m][tp.n + 1][tp.h] == 0) {
                q.push(Point(tp.m, tp.n + 1, tp.h));
                map[tp.m][tp.n + 1][tp.h] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h - 1));
                map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            if (tp.h + 1 <= H && map[tp.m][tp.n][tp.h + 1] == 0) {
                q.push(Point(tp.m, tp.n, tp.h + 1));
                map[tp.m][tp.n][tp.h + 1] = map[tp.m][tp.n][tp.h] + 1;
                sw = true;
                remain--;
            }
            result = sw ? max(result, map[tp.m][tp.n][tp.h] + 1) : result;
        }
    }

로직은 길어 보이지만 간단하다.

그냥 BFS를 돌리는 로직이며 마지막에 result는 현재 level이 최고 level보다 크다면 갱신시켜주는 작업이다.

보통 BFS를 돌릴 때 level정보는 저장하는 방법이 두가지가 있다.

하나는 좌표(Graph나 map)에 직접 적는 방법과 클래스(위의 경우 Point)에 레벨 변수를 두고 넣는 방법이다.

이 문제가 더러운 이유는 레벨 변수를 둘 수가 없기 때문이다.

그래서 좌표에 직접 써야한다.

따라서 위의 경우 익으면 1이 아니라 익으면 1 이상이 들어가게 로직이 짜져있다.

if (0 < tp.h - 1 && map[tp.m][tp.n][tp.h - 1] == 0) {
    q.push(Point(tp.m, tp.n, tp.h - 1));
    //map[tp.m][tp.n][tp.h - 1] = 1;
    map[tp.m][tp.n][tp.h - 1] = map[tp.m][tp.n][tp.h] + 1;
    sw = true;
}

가령 하나를 예를 들어서 3번째 줄을 보면 위의 코드는 만약 현재 탐색하려는 좌표가 빈공간이면

지금 좌표의 값에 1을 더해주는 로직이다.

원래라면 주석처리한것 처럼 해도 되지만 이 경우 현재 레벨에 대한 정보는 소실된다.

즉 지금 일어난 루프가 몇번째 레벨인지를 알 도리가 없다.

이 경우 클래스에 저장해 두는데 이게 메모리 제한으로 막아놨다.

그래서 우리는 현재 레벨에 대한 정보를 좌표에 저장해둔다(위의 예제는 변수 map).

//output
    {
        if (remain == 0) {
            cout << result - 1 << endl;
        } else {
            cout << -1 << endl;
        }
    }

그래서 마지막에 결과에서 1을 뺀다.

왜냐하면 기존 토마토가 존재한다는걸 좌표에서 1로 표현,

그 다음은 1씩 증가하게 되는데 결과 값에서 기존의 값 1이 최대값이므로 1을 빼줘야하기 때문이다.

https://www.acmicpc.net/problem/9095

이 문제는 백준 DP중 가장 많이 푼 문제이며 한편으론 DP로 풀지 않아도 되는 이상한 문제이다.

일단 이 문제는 초보자가 풀기에는 딱 좋은 문제인데 어떻게 푸는지 보도록 하자.

특정 정수 N을 만들기 위해서 0에서 붙어 1혹은 2혹은 3을 더하는 문제이다.

즉 1혹은 2혹은 3을 더하여 N을 만들 수 있는 경우의 수를 모두 찾는 것이다.

이 문제는 모든 경우의 수를 계산하는 완전탐색(브루트포스)를 이용하여 풀 수 있다.

다만 원래라면 시간 제한에 걸리게되는데 여기서는 N의 상한선이 11밖에 되지 않는다.

4를 구하는 방법

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

총 7가지

모든 경우의 수를 나열하는 문제는 트리를 그려가면서 보면 위처럼 나온다.

위는 4를 구하는 방법인데 총 7가지가 나오는걸 알 수 있다.

시간 복잡도는 일반적으로 계산하면 O(3^N)이 나오게된다.

하지만 실제로 계산해보면 3^N보다는 월등히 적게 계산하는데 그 이유는 안하는 경우의 수가 매우 많기 때문이다.

다 계산해야 실제 시간복잡도를 알 수 있지만 여기서는 패스하겠다.

어쨋든 일반적인 완전탐색을 사용할경우 어마어마한 시간을 사용하는걸 알 수 있다.

완전탐색을 하는 방법은 재귀함수를 이용하는 방식(메모이제이션)과 for문을 이용한 방식(타뷸레이션)이 있다.

여기서는 메모이제이션을 이용한 방식으로 푸는 법을 알아보자.

void f(int n) {
    if (n == N) {
        cnt++;
    }

    if (n + 3 <= N) {
        f(n + 3);
    }
    if (n + 2 <= N) {
        f(n + 2);
    }
    if (n + 1 <= N) {
        f(n + 1);
    }
}

재귀함수를 짜본적이 없다면 지금부터라도 익숙해 져야한다.

재귀를 짜려면 종료되야하는 지점인 배이스 케이스를 먼저 작성해야한다.

이 모든 경우의 수를 구하는 재귀 함수 f는 0부터 시작해서 특정한 수 N을 완성해 나갈것이다.

그리고 그 N이 되면 더이상 함수를 실행하지 않고 종료를 할것이다.

그리고 마지막 경우에 도달했다면 cnt를 늘려준다.

#include <iostream>
#include <vector>

using namespace std;

int T;
int N;
vector<int> ARR;
vector<int> results;
int cnt;
int tmp;

void f(int n) {
    if (n == N) {
        cnt++;
    }

    if (n + 3 <= N) {
        f(n + 3);
    }
    if (n + 2 <= N) {
        f(n + 2);
    }
    if (n + 1 <= N) {
        f(n + 1);
    }
}

int main() {
    //init
    {
        cin >> T;
        ARR.push_back(0);
        results.push_back(0);
        for (int t = 1; t <= T; t++) {
            cin >> tmp;
            ARR.push_back(tmp);
        }
    }

    //logic
    {
        for(int t=1;t<=T;t++){
            cnt = 0;
            N = ARR[t];
            f(0);
            results.push_back(cnt);
        }
    }

    //output
    {
        for(int t=1;t<=T;t++){
            cout << results[t] << endl;
        }
    }
    return 0;
}

이 코드를 사용해서 문제를 풀면 두가지의 문제점이 있다.

먼저 시간복잡도가 O(3^N)으로 매우 높다는점, 그리고 큰 수를 사용할 수 없다는 점이다.

하지만 이 문제로 백준에 넣어도 통과는 되는데 그 이유는 11까지 밖에 연산하지 않기 때문이다.

11까지 연산량은 필자가 직접해본결과 1104번 밖에 돌지 않는데 이는 1초도 걸리지 않기 때문에 충분한 시간이다.

그래서 사실 이 문제는 DP를 도입하지않고 완전탐색만으로 풀 수 있는 쉬운 문제이다.

괜히 정답률이 60%대가 아니라는 이야기이다.

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

int T;
int N;
ll cnt;
vector<ll> memo;

ll f(int n) {
    if (n == N) {
        return 1;
    } else {
        ll result = 0;
        if (n + 3 <= N) {
            if (memo[n + 3] == 0) {
                memo[n + 3] = f(n + 3);
            }
            result += memo[n + 3];
        }
        if (n + 2 <= N) {
            if (memo[n + 2] == 0) {
                memo[n + 2] = f(n + 2);
            }
            result += memo[n + 2];
        }
        if (n + 1 <= N) {
            if (memo[n + 1] == 0) {
                memo[n + 1] = f(n + 1);
            }
            result += memo[n + 1];
        }
        return result;
    }
}

int main() {
    //init
    {
        cin >> T;
    }

    //repeat
    for (int t = 1; t <= T; t++) {
        //init
        {
            cin >> N;
            cnt = 0;
            memo.clear();
            memo.resize(N + 1, 0);
        }

        //logic
        {
            cnt = f(0);
        }

        //output
        {
            cout << cnt << endl;
        }
    }
    return 0;
}

그럼 메모이제이션을 도입하고 숫자를 큰 숫자도 가능하게 하려면 위처럼 코드를 짜면된다.

실제 여러분의 코드는 30이상부터 엄청나게 오랜시간동안 연산을 하게 될것이다.

또한 40이상의 수는 오버플로우로 제대로 표현 못할것이다.

문제 조건상 11이하의 수가 들어가므로 위의 처리를 안해줘도 무방하지만,

여러분이 DP를 배우는 입장에서 메모이제이션은 익히는게 좋다.

if (n + 3 <= N) {
    result += f(n + 3);
}

메모이제이션이 뭔지 알려면위의 코드를 보자.

우리는 f(n+3)의 결과값을 구하고싶다.

하지만 이는 중복계산될 수 있다.

f(n+3)이 여러번 호출될 가능성이 있다.

문제는 f(n+3)은 또다시 f(n+3+1),f(n+3+2),f(n+3+3)을 호출할 가능성이 생긴다.

물론 아래의 녀석들도 자식들을 3개씩 더 호출할 수 있다.

이렇게 중복 호출을 막으려면 이 때의 값을 저장해 놓는 것이다.

이를 메모이제이션이라고한다.

if (n + 3 <= N) {
    if (memo[n + 3] == 0) {
        memo[n + 3] = f(n + 3);
    }
    result += memo[n + 3];
}

이렇게 memo[n+3]이 있는지 확인하고(0이 아닌지확인하고) 0이라면 함수를 계산해서 값을 넣는다.

만약에 0이 아니라면 이미 구했던 것이므로 메모의 값을 넣는다.

#include <iostream>
#include <vector>

using namespace std;

int T;
int N;
vector<int> ARR;
vector<int> memo;
vector<int> results;
int tmp;
int result;

int main() {
    //init
    {
        cin >> T;
        ARR.push_back(0);
        results.push_back(0);
    }

    //repeat
    for (int t = 1; t <= T; t++) {
        //init
        {
            cin >> tmp;
            ARR.push_back(tmp);
            N = ARR[t];
            memo.clear();
            memo.resize(N + 1, 0);
            memo[0] = 1;
        }

        //logic
        {
            for (int n = 1; n <= N; n++) {
                result = 0;
                if (n - 1 >= 0) {
                    result += memo[n - 1];
                }
                if (n - 2 >= 0) {
                    result += memo[n - 2];
                }
                if (n - 3 >= 0) {
                    result += memo[n - 3];
                }
                memo[n] = result;
            }
            results.push_back(memo[N]);
        }

        //output
        {
            cout << results[t] << endl;
        }
    }

    return 0;
}

만약 나는 재귀함수가 아닌 for문을  쓰고싶다면 for문을 써도 무방하다.

같은 로직을 for문으로 짠 것이다.

여기서도 memo에 넣는데 for문과 재귀의 차이점은

재귀는 필요한 것만 계산하고(모두를 계산하지는 않음)

for문은 필요하건 안하건 모두를 계산하게된다.

모두를 구하지 않는다면 재귀가 시간이 더 빠르게 된다.

다만 보통 알고리즘 테스트에서는 모두를 다 구하게 하므로 for문을 쓰는 방법 역시 유효하다.

이렇게 미리 모든 값을 다 구하는 것은 메모이제이션이라고 하지 않고 타뷸레이션이라고 한다.

메모이제이션이나 타뷸레이션이나 둘다 메모이제이션이라고 부르는 경향이 있어서 적당히 알아들으면된다.

https://www.acmicpc.net/problem/1463

이 문제는 백준에서 동적계획법(다이나믹 프로그래밍)문제 중에서는 가장 위에 있는 문제이며 가장 유명한 문제이다.

난이도는 동적계획법중에서 가장 쉬운 편이기에 초보자들에게 많이 추천받는 문제이기도 하다.

시간 제한은 2초로 널널한편, 동적계획법만 효율적이게 작동한다면 무조건적으로 해결되는 시간이다.

또한 메모리제한도 256메가는 아니지만 신경쓸 정도는 아니다. 정답률은 32퍼로 동적계획법이라는점, 사람들이 많이푼다는점.

두개를 종합해 봤을 때 정답률 역시 높은 편이라고 볼 수 있다.(단 일반적으로 32퍼는 낮은 확률에 속한다.)

1.X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이 문제는 위의 세가지 경우를 반복한다.

즉 어떤 수 X가 주어졌을 때 위의 위의 연산을 통해서 1을 만드는데 그중에서 최솟값을 출력하면된다.

7을 예시로 들어보자.

괄호안의 숫자는 아래를 뜻한다

1 - 3으로 나눔

2 - 2로 나눔

3 - 1로 뺌

7->(1)불가능
7->(2)불가능
7->(3)6->(1)2->(1)불가능
7->(3)6->(2)3->(1)1
7->(3)6->(3)5->(1)불가능
7->(3)6->(3)5->(2)불가능
7->(3)6->(3)5->(3)4->(1)불가능
7->(3)6->(3)5->(3)4->(2)2->(1)불가능
7->(3)6->(3)5->(3)4->(2)2->(2)1
7->(3)6->(3)5->(3)4->(2)2->(3)1
7->(3)6->(3)5->(3)4->(3)3->(1)1
7->(3)6->(3)5->(3)4->(3)3->(2)불가능
7->(3)6->(3)5->(3)4->(3)3->(3)2->(1)불가능
7->(3)6->(3)5->(3)4->(3)3->(3)2->(2)1
7->(3)6->(3)5->(3)4->(3)3->(3)2->(3)1

7이 가능한 경우의 수를 한번 보도록하자.

불가능한 경우를 도달한것을 센다면 7의 경우15가지, 불가능한 경우를 도달한 것을  뺀다면 6가지의 경우의 수 이다.

시간복잡도는 항상 최악으로 계산하는데 보면 알겠지만 3^7개까지의 경우의 수를 나열하므로

시간복잡도 계산시에는 O(3^n)로 계산하게 된다.

다만 실제로는 저 시간복잡도에 한참 못미치는데 그 이유는 실제 숫자가 2나 3으로 안나눠지는 경우가 아주 많기 때문에

기하 급수적으로 경우의 수가 줄어들긴 한다.

일단 중요한건 그냥 완전탐색(브루트포스로)문제를 풀줄 알아야한다.

그러면 위의 시간복잡도로 풀 수 있다.

그러면 우리는 공간복잡도를 이용해서 시간 복잡도를 줄 일 수 있다.
어떻게 시간을 줄이냐면 "중복된 계산"을 저장한 후 나중에 함수 호출해야할 경우 함수를 호출안하고 계산된 값을 주는 것이다.

즉 일종의 캐싱전략이고 이를 메모이제이션이라고 부른다.

아래 예시를 보자

괄호안의 숫자는 아래를 뜻한다

1 - 3으로 나눔

2 - 2로 나눔

3 - 1로 뺌

대괄호안의 숫자는 체크해야할 이전 값이다.

7을 예시로 생각하면 문제는 아래처럼 생각할 수 있다.

1이라면 최소값이 0이다.
-(1)은 불가능
-(2)은 불가능
-(3)은 불가능

2의 경우 최소값은 1이다.
-(1)은 불가능
-(2)의 결과값[1] : 0
-(3)의 결과값[1] : 0
-최소 값은 [1]의 0이므로 여기서 +1 해준다.

3의 경우 최소값은 1이다.
-(1)의 결과값[1] : 0
-(2)는 불가능
-(3)의 결과값[2] : 1
-최소 값은 [1]의 0이므로 여기서 +1 해준다.

4의 경우 최소값은 2이다.
-(1)은 불가능
-(2)의 결과값[2] : 1
-(3)의 결과값[3] : 1
-최소 값은 [2]나 [3]의 1이므로 여기서 +1 해준다.

5의 경우 최소값은 3이다.
-(1)은 불가능
-(2)는 불가능
-(3)의 결과값[4] : 2
-최소 값은 [4]의 2이므로 여기서 +1 해준다.

6의 경우 최소값은 2이다.
-(1)의 결과값[2] : 1
-(2)의 결과값[3] : 1
-(3)의  결과값[5] : 3
-최소 값은 [2]나 [3]의 1이므로 여기서 +1 해준다.

7의 경우 최소값은 3이다.
-(1)은 불가능
-(2)는 불가능
-(3)의 결과값[6] : 2
-최소값은 [6]의 2이므로 여기서 +1 해준다.

여러분은 분할정복기법으로 이 문제를 접근할 수 있어야한다.

7의 결과를 아는 것은 6의 최소값을 아는   것과 동일한 문제다.

6의 결과값을 아는 것은 5의 최소값을 아는 것과 동일한 문제이다.

이렇게 1까지 내려가면된다.

이를 코드로 구현하는 방법은 재귀와 for문이 있다.

마술 같게도 DP를 도입하면 시간복잡도는 O(n)이된다. 단 공간복잡도는 O(n)으로 늘어나게 된다.

#include <iostream>
#include <vector>

#define INF 0x7fffffff
using namespace std;

int N;
vector<int> memo;
int result;

int mi(int x, int y) {
    return x < y ? x : y;
}

int f(int n) {
    if (n == 1) {
        return 0;
    } else {
        int min_val = INF;
        if (n % 3 == 0) {
            if (memo[n / 3] == -1) {
                memo[n / 3] = f(n / 3);
            }
            min_val = mi(min_val, memo[n / 3]);
        }
        if (n % 2 == 0) {
            if (memo[n / 2] == -1) {
                memo[n / 2] = f( n / 2);
            }
            min_val = mi(min_val, memo[n / 2]);
        }
        if (n - 1 >= 1) {
            if (memo[n - 1] == -1) {
                memo[n - 1] = f(n - 1);
            }
            min_val = mi(min_val, memo[n - 1]);
        }
        return min_val + 1;
    }
}

int main() {
    //init
    {
        cin >> N;
        memo.resize(N + 1, -1);
    }

    //logic
    {
        result = f(N);
    }

    //output
    {
        cout << result << endl;
    }

    return 0;
}

재귀로 푸는 방법은 위와 같다.

#include <iostream>
#include <vector>

#define INF 0x7fffffff
using namespace std;

int N;
vector<int> memo;
int result;

int mi(int x, int y) {
    return x < y ? x : y;
}

int main() {
    //init
    {
        cin >> N;
        memo.resize(N + 1, -1);
        memo[1] = 0;
    }

    //logic
    {
        for (int n = 2; n <= N; n++) {
            result = INF;
            if (n % 3 == 0) {
                result = mi(result, memo[n / 3]);
            }
            if (n % 2 == 0) {
                result = mi(result, memo[n / 2]);
            }
            if (n - 1 >= 1) {
                result = mi(result, memo[n - 1]);
            }
            memo[n] = result + 1;
        }

    }

    //output
    {
        cout << memo[N] << endl;
    }

    return 0;
}

for문을 이용해서 푸는 방법은 위와 같다.

https://www.acmicpc.net/problem/10942

백준 문제 특유의 거지같은 빡센 시간제한과 용량제한이 있는 문제이다.

이렇게 시간이 극단적으로 적을 때는 c++에서 cin, cout을 사용하면 시간이 모자라게 된다.

다행히도 vector를 배열로 써야하거나 그런 상황까지는 오지 않는다.

어쨋든 위의 조건때문에 틀렸다면 cin,cout을 printf와 scanf로 바꾸면 아주 쉽게 통과할 것이다.

질문 M개의 갯수의 제한이 백만개나 되기 때문에 0.5초는 매우 빡빡하다.

따라서 질문을 저장해놓고 쓴다던지(vector나 배열) 질문의 입출력이 cin, cout을 사용한다면 이미 그것만으로 시간은 넘친다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

일단 팬린드롬이 뭔지부터 알아야한다.

팰린드롬이란 대칭성을 이루는 문자열을 의미한다. 이를 한국말로는 회문이라한다.

이를 검사하는 것이다.

1 2 1 3 1 2 1

가령 위와 같은 회문은 팰린드롬이다.

다만 문제이서 묻는 것은 부분부분 봤을때도 회문이냐?

즉 부분집합도 팰린드롬을 이루는가이다.

먼저 시간,공간을 무시하고 팰린드롬을 풀어보자.

특정 문자열이 팰린드롬인지 아는 방법은 시작을 s라 잡고 끝을 e라잡았을때 동시에 시작과 끝을 비교하고 한칸씩 서로 땡긴다.

#1. (1) 2 1 3 1 2 (1)
#2. 1 (2) 1 3 1 (2) 1
#3. 1 2 (1) 3 (1) 2 1
#4. 1 2 1 ((3)) 1 2 1

이 동작은 특정 문장의 길이를 n이라 가정할 때 O(n/2)의 시간복잡도, 즉 O(n)이 걸리게된다.

이러한 작업을 모든 경우의 수를 따진다면 총 n*n의 경우의 수가 있다. 즉 모든 작업의 수는 O(n^2)이 된다.

그러면 O(n)*O(n^2)이므로 O(n^3)이라는 미친 시간복잡도가 걸리게된다.

시간을 줄이는 방법은 크게 보면 greedy와 dp가 존재한다.

하지만 해당방법은 아무리 봐도 greedy는 힘들 것 같다. 추가적인 조건이 걸려있지 않기 때문이다.

그렇다면 dp로 푸는수 밖에 없다.

하지만 dp로 풀이방법이 쉬이 떠오르지 않을 수 있다.

일반적인 재귀의 진행방식과 조금 차이가 있다.

팰린드롬을 분할정복하려면 어떻게 해야할까??

#1. (1) 2 1 3 1 2 (1) -> 2 1 3 1 2가 팰린드롬이면 양 끝만 비교하면된다.
#2. 1 (2) 1 3 1 (2) 1 -> 1 3 1이 팰린드롬이면 양 끝만 비교하면된다.
#3. 1 2 (1) 3 (1) 2 1 -> 3이 팰린드롬이면 양 끝만 비교하면된다.
#4. 1 2 1 ((3)) 1 2 1 -> 1자릿숫자는 무조건 팰린드롬이다.

사실 우리가 진행했던 방식에 힌트가 있다.

특정 회문을 level별로 생각해보자. 가령위를 예로 들자면

1레벨상황에서 2레벨 상황의 값을 안다면 서로 양쪽만 비교하면 된다.

2레벨 상황에서도 3레벨 상황의 값을 안다면 서로 양쪽만 비교하면 된다.

4레벨 상황에서는 한자리이므로 무조건 팰린드롬이다.

이 방식을 생각해보면 재귀의 진행방향을 알 수 있다.

먼저 시작점 s와 종착점 e의 거리가 d라고 가정하자. d가 0이라면, 무조건 펠린드롬이다.

비교도 할 필요없다. 즉 s==e라면 무조건 팰린드롬이다.

그럼 d가 1이라면 어떻게 될까? 이 경우는 s와 e의 값을 비교하면된다. 둘이 동등하면 팰린드롬이다.

그 이상이라면?

1.양 끝값이 동등하며
2.양 끝값을 제외한 그 사이 까지의 값이 팰린드롬이라면
3.팰린드롬이다.

이제 분할정복을 할 수 있다.

그냥 돌리면 중복된 수많은 경우의 수가 생기며 따라서 나머지는 메모이제이션을 해주면 된다.

dp를 적용할 경우 시간복잡도는 O(n^2) + O(m)이 되는데 n은 2,000이고 m은 1,000,000 결국 O(n^2)라 봐도 무방하다.

대신 공간 복잡도가 O(n^2)로 늘어나게된다. 기존에는 O(n)이였다.

다만 문제의 조건이 256mb이며 n^2의 상한선이 4,000,000이므로 용량은 아주 충분하다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> ARR;
int tmp;
int ts, te;

vector<vector<int>> memo;

int main() {

    //init
    {
        scanf("%d", &N);
        ARR.push_back(0);
        for (int n = 1; n <= N; n++) {
            cin >> tmp;
            ARR.push_back(tmp);
        }
        scanf("%d", &M);
        memo.resize(N + 1, vector<int>(N + 1, -1));
    }

    for (int d = 0; d < N; d++) {
        for (int s = 1; s <= N - d; s++) {
            if (d == 0) {
                memo[s][s] = 1;
            } else if (d == 1) {
                memo[s][s + d] = ARR[s] == ARR[s + d];
            } else {
                memo[s][s + d] = memo[s + 1][s + d - 1] ? ARR[s] == ARR[s + d] : 0;
            }
        }
    }

    for (int m = 1; m <= M; m++) {
        scanf("%d %d", &ts, &te);
        printf("%d\n", memo[ts][te]);
    }

    return 0;
}

위의 코드는 for문을 사용한 코드이다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> ARR;
int tmp;
vector<vector<int>> memo;


int func(int s, int e) {
    if (s == e) {
        memo[s][e] = 1;
        return 1;
    } else if (s + 1 == e) {
        return memo[s][e] = ARR[s] == ARR[e];
    } else {
        if (memo[s + 1][e - 1] == -1) {
            memo[s + 1][e - 1] = func(s + 1, e - 1);
        }
        return memo[s][e] = memo[s + 1][e - 1] ? ARR[s] == ARR[e] : 0;
    }
}

int main() {

    //init
    {
        scanf("%d", &N);
        ARR.push_back(0);
        for (int n = 1; n <= N; n++) {
            cin >> tmp;
            ARR.push_back(tmp);
        }
        scanf("%d", &M);
        memo.resize(N + 1, vector<int>(N + 1, -1));
    }

    int ts, te;

    for (int m = 1; m <= M; m++) {
        scanf("%d %d", &ts, &te);
        if (memo[ts][te] == -1) {
            memo[ts][te] = func(ts, te);
        }
        printf("%d\n", memo[ts][te]);
    }

    return 0;
}

해당 코드는 재귀로 구현한 코드이다.