BOJ 16568

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

 

dp로도 풀수 있고, bfs로도 풀 수 있다.

 

나는 처음에 완전탐색으로 접근했다가 시간초과가 나왔다. n의 범위가 너무 크니, 어찌보면 당연하다.

그 후 , dp로 풀었는데 잘 안풀려서 bfs로 풀었다.

그리고 bfs로 풀어서 통과한 후, Dp로 다시 풀었다. 

 

bfs로 푸는건 정석적인 Bfs처럼 풀면 된다.

#include <bits/stdc++.h>
using namespace std;
int N, A, B;
int mn = 10000001;
int visited[1000004];

// 처음 완전탐색으로 했을때. 시간초과남.
void go(int n, int a, int b, int cnt)
{
    if (n < 0)
    {
        return;
    }
    if (n == 0)
    {
        mn = min(mn, cnt);
        return;
    }

    go(n - 1 - b, a, b, cnt + 1);
    go(n - 1 - a, a, b, cnt + 1);
    go(n - 1, a, b, cnt + 1);
}

// bfs
void bfs(int a, int b)
{
    queue<int> q;
    q.push(0);
    visited[0] = 1;
    while (q.size())
    {
        int cur = q.front();
        int curD = visited[cur];
        q.pop();
        if (cur == N)
        {
            mn = min(mn, curD);
            continue;
        }
        for (int next : {cur + 1, cur + a + 1, cur + b + 1})
        {
            if (next <= N && (!visited[next] || visited[next] > curD + 1))
            {
                q.push(next);
                visited[next] = curD + 1;
            }
        }
    }
}

int main()
{
    cin >> N >> A >> B;
    // go(N, A, B, 0);
    // dp[N] = 0;
    bfs(A, B);

    cout << mn - 1 << "\n";

    return 0;
}

 

그리고 Dp로도 풀어봤는데, 이때는 냅색문제 풀듯이 풀었다.

#include <bits/stdc++.h>
using namespace std;
int N, A, B;
int mn = 10000001;
int dp[1000004]; // 위치가 n일때의 최소 초

int main()
{
    cin >> N >> A >> B;
    // go(N, A, B, 0);

    for (int i = 1; i <= N; i++)
    {
        dp[i] = dp[i - 1] + 1;
        if (i - A - 1 >= 0)
        {
            dp[i] = min(dp[i - A - 1] + 1, dp[i]);
        }
        if (i - B - 1 >= 0)
        {
            dp[i] = min(dp[i - B - 1] + 1, dp[i]);
        }
    }

    cout << dp[N] << "\n";

    return 0;
}

 

시간차이는 거의 없다. 의미없는 정도. 위가 Dp로 풀었을 때, 아래가 Bfs로 풀었을 때