✅ 한 것들

---

• 백준
• 면접 대비 : 질문 시뮬
• 프로그래머스

⚔️ 백준

---

• n과 m (1)
• 파티
  • 문제 처음부터 끝까지 읽기. '오고 가는' 비용인데 그냥 가는 비용이라고 생각해버렸다.
  • 다익스트라는 pq에 간선 비용이 아니라 전체 비용 넣는 것
  • 최댓값 초기화할 때 충분히 큰 값 넣었는지 생각
• 벼락치기
  • knapsack 문제
  • if (time > j) dp[i][j] = dp[i - 1][j];에서 부등호 방향 실수
  • dp[i][j] = max(dp[i-1][j], dp[i - 1][j - time] + score);에서 dp[i-1][j] 을 dp[i][j]로 해버린 실수

⚔️ 프로그래머스

---

GPS

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

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

int answer;
int goal;
vi minRem;
vvi edge;

void SetMinRem(int end, int k)
{
    // end에서 bfs 때리면서 cnt를 기록해둔다
    // rem이 minRem보다 작은데 그곳에 아직 있다면 배제
    queue<int> q;
    vb visited = vb(k+1);
    q.push(end);
    visited[end]= true;
    int cnt = -1;
    while(!q.empty())
    {
        cnt++;
        int len = q.size();
        while(len--)
        {
            int node = q.front(); q.pop();
            minRem[node] = cnt;
            for(int next : edge[node])
            {
                if(visited[next]) continue;
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

void dfs(int err, int rem, int cur, int& k, vi& gps_log)
{
    if(cur != gps_log[k-rem-1]) err++;
    if(err >= answer) return;
    if(rem < minRem[cur]) return;
    if(rem==0)
    {
        if(cur==goal) answer = min(err,answer);
        return;
    }
    
    for(int next : edge[cur])
    {
        dfs(err,rem-1,next,k,gps_log);
    }
}

int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    answer = k+1;
    // ! 승차 위치와 하차 위치는 고정 !
    // dfs로 모든 경로를 구한다 (탐색 중 t 이상이 되거나 도착했는데 t가 아니면 취소)
    // 모든 경로와의 오차를 계산하고, 최소 오차를 반환한다
    // 최적화 : 도착점에서부터 bfs를 해서, rem이 그에 미치지 못하면 바로 반환
    // 최적화 2 : 경로가 아니라 err, cur, rem만 갖고 다닌다
    // 최적화 3 : err가 answer보다 커지면 return
    edge = vvi(n+1);
    for(int i=1; i<=n; i++)
    {
        edge[i].push_back(i);
    }
    for(vi e : edge_list)
    {
        edge[e[0]].push_back(e[1]);
        edge[e[1]].push_back(e[0]);
    }
    int start = gps_log[0];
    goal = gps_log[k-1];
    minRem = vi(n+1);
    SetMinRem(goal,k);
    dfs(0,k-1,start,k,gps_log);
    if(answer==k+1) answer=-1;
    return answer;
}

할 수 있는 최적화는 다 해봤는데 시간 초과.

정답 찾아보니 dp였다.
minRem은 없어도 되고, err로 기록하고 있는 거 최솟값을 dp로 저장해놓고 더 크면 배제해야 한다.
재귀에서 조건 기반으로 배제할 때 dp 쓸 수 있다는거 머리에 넣어두면 좋을듯.

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

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

int answer;
int goal;
vvi edge;
vvi dp;

void dfs(int err, int rem, int cur, int& k, vi& gps_log)
{
    if(cur != gps_log[k-rem-1]) err++;
    
    if(err >= dp[rem][cur]) return;
    else dp[rem][cur] = err;
        
    if(rem==0)
    {
        if(cur==goal) answer = min(err,answer);
        return;
    }
    
    for(int next : edge[cur])
    {
        dfs(err,rem-1,next,k,gps_log);
    }
}

int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    answer = k+1;
    edge = vvi(n+1);
    for(int i=1; i<=n; i++)
    {
        edge[i].push_back(i);
    }
    for(vi e : edge_list)
    {
        edge[e[0]].push_back(e[1]);
        edge[e[1]].push_back(e[0]);
    }
    int start = gps_log[0];
    goal = gps_log[k-1];
    dp = vvi(k+1,vi(n+1,1e9));
    dfs(0,k-1,start,k,gps_log);
    if(answer==k+1) answer=-1;
    return answer;
}

dp로 금방 전환해서 풀이 성공