dp가 잠깐 생각 나긴했지만, dp[i]를 적고 풀어보려했다.
dp[i]와 dp[i-1]과 dp[i+1] dp[i/2]의 연관성을 찾아 관계식을 도출해 내서 반복문을 통해 dp[i]를 채워나가면 문제가 풀릴거 같았다. 하지만 앞으로 뒤로 갈수있는 양방향 문제에서 어떻게 짜야할지 얘매했고, 반복을 계속하면서 최신화 완료됫을때 루프를 나오는 방식으로 문제를 해결할수 있지만, 이런문제를 DP로 접근하는건 별로 좋지 않았다.
n-1, n+1, n2를 큐에 넣고빼고를 반복하면서 k에 접근해 가는 방식이다.
이렇게되면 O(3^a)으로 시간초과가 날까 걱정햇지만 그렇지 않았다. n이 100,000보다 작거나 같고, 2가 섞여있어서 그런거같다.
중복체크를 해주지 않으면 메모리 초과가 난다.
큐에 넣을때 중복이 있는지 체크하려고 큐전체를 체크하는건 비효율적이고,
exCheck[i]처럼 이미 체크가 됬던곳인지 아닌지를 체크해주면 된다.
exCheck의 범위를 넘을 수 없다. 여기서는 exCheck의 범위가 MAX 인덱스까지이므로
MAX-1까지 넣어줘야하므로, x2,x3< MAX 이고, x1>=0이다.
몇번만에 k에 도착했는지를 기록해야한다.
처음에는 while(q.empty())반복문 안에 cnt 를 하나씩 올렷는데 그렇게 접근하면
큐를 세번씩 넣고 돌리기 때문에 cnt가 과도하게 많이 증가한다.
처음부터 큐에 넣을때 pair<int,int>자료형으로 위치와 횟수자체를 기록해야 한다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"
#define MAX 100001
int n, k;
queue<pair<int,int>> q;
bool exCheck[MAX];
int bfs() {
q.emplace(n,0 );
while (!q.empty())
{
int locate = q.front().first;
int cost = q.front().second;
q.pop();
if (locate == k)
{
return cost;
}
int x1 = locate - 1;
int x2 = locate + 1;
int x3 = locate * 2;
if (x1 >= 0 && !exCheck[x1])
{
exCheck[x1] = true;
q.emplace( x1, cost + 1 );
}
if (x2 <MAX && !exCheck[x2])
{
exCheck[x2] = true;
q.emplace(x2, cost + 1 );
}
if (x3 <MAX && !exCheck[x3])
{
exCheck[x3] = true;
q.emplace( x3, cost + 1 );
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
cin >> n >> k;
cout << bfs();
}
https://hevton.tistory.com/422 풀이참고
https://meansoup.blogspot.com/2017/05/1697.html 알고리즘DP를 이용하는방법