[C++]백준 16568번 엔비스카의 영혼

📌문제 링크

---

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

📌문제 설명

---

dp와 그래프 탐색 모두 가능합니다. 문제를 읽으면 흐름을 따라가면 자연스럽게 점화식이 도출됩니다. 필자는 bfs탐색으로 문제를 해결했습니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int N, a, b, arr[1000001]; // N: 목표 값, a, b: 더할 값, arr: 최소 횟수를 저장할 배열

// 입력 함수
void input(){
    cin >> N >> a >> b; // N, a, b 입력
}

// 초기화 함수
void init(){
    for(int i = 1; i <= N; i++){
        arr[i] = INT_MAX; // 배열을 최대값으로 초기화
    }
}

// 너비 우선 탐색 함수
int bfs(){
    queue<pair<int, int>> q; // 큐 선언
    q.push({0, 0}); // 시작점 (0, 0) 추가
    arr[0] = 0; // 시작점의 최소 횟수는 0

    while(!q.empty()){
        auto [cur, cnt] = q.front(); // 현재 위치와 횟수
        q.pop();

        // 현재 위치에서 1 증가
        if(++cur <= N && arr[cur] > ++cnt){
            arr[cur] = cnt; // 최소 횟수 갱신
            q.push({cur, cnt}); // 큐에 추가
        }

        if(cur >= N){
            continue; // 목표 값을 넘으면 계속
        }

        // 현재 위치에서 a 증가
        if(cur + a <= N && arr[cur + a] > cnt){
            arr[cur + a] = cnt; // 최소 횟수 갱신
            q.push({cur + a, cnt}); // 큐에 추가
        }

        // 현재 위치에서 b 증가
        if(cur + b <= N && arr[cur + b] > cnt){
            arr[cur + b] = cnt; // 최소 횟수 갱신
            q.push({cur + b, cnt}); // 큐에 추가
        }
    }

    return arr[N]; // 목표 값에 도달하는 최소 횟수 반환
}

void solve(){
    input();
    init();
    cout << bfs();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}