[BOJ/C++] 22871: 징검다리 건너기

🥈 Silver 1

✏️ 1차 솔루션

⭐️ 이분 탐색으로 풀이

1. left 는 가장 왼쪽 인덱스, right 는 가장 오른쪽 인덱스로 정의
2. mid 구하기
3. left-mid 의 비용과 left-right 의 비용 비교
   1) left-right 의 비용이 더 크면 mid 를 거치는 것이 효율적인 방법이므로 이때 비용은 ans 에 최대값 비교해서 저장해두고 mid 이후 돌들을 판단하기 위해 left = mid 로 갱신
   2) left-mid 의 비용이 더 크거나 left 다음에 바로 right 라면 마지막 돌까지 바로 가는 것이 더 효율적인 방법이라는 것이므로 이때 비용 ans 에 최대값 비교해서 저장하고 break

🚨 1차 trouble

방법이 맞는지는 모르겠으나 오답
정확한 풀이방법이 감이 오지 않음

✏️ 최종 솔루션

⭐️ dp 로 풀이

1. 모든 돌을 탐색하면서 현재 돌에서 갈 수 있는 오른쪽 돌에 대해 오른쪽 돌을 곧장 가는 방법과 오른쪽 돌까지 가는 루트 중에 최대값을 오른쪽 돌을 거치는 루트 비용으로 보고 오른쪽 돌들 중에 비용이 가장 적은 것을 현재 돌의 비용으로 산출
   ❗️ 현재 돌의 비용을 계속 갱신하게 되는데 이 값이 dp 에도 계속 갱신될 수 있도록 최적 비용 갱신 변수는 dp 를 참조 ➡️ long long& cur=dp[a];
2. 현재 돌에서 갈 수 있는 오른쪽 돌까지의 최적 루트를 계산하기 위해 오른쪽 돌을 재귀로 넣어서 계산하고 그 값을 현재 돌에서 오른쪽 돌까지 직행하는 비용과 비교해야 하기 때문에 오른쪽 돌의 최적 비용을 재귀로 먼저 구하기

📌 self feedback

이분탐색으로 접근해서 잘못된 방법으로 풀이
잘 시도해보지 않았던 풀이방법이라서 이해하기 어려웠음. 비슷한 유형으로 연습이 필요하고 이분 탐색에 아직 익숙해지지 않음
참조형 변수를 활용하여 굳이 dp 에 현재 위치를 갱신해주는 작업을 하지 않아도 괜찮았음. 참조형 변수를 적극적으로 활용하면 좋을 것 같음

✏️ 최종 code

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int n;
long long dp[5001];
long long stone[5001];

long long go(int a) {
    if(a==n-1) return 0;
    long long& cur=dp[a];
    if(cur!=0) return cur;
    
    cur=1e10;
    for(int i=a+1;i<n;i++) {
        cur=min(cur,max(go(i),(i-a)*(1+abs(stone[i]-stone[a]))));
    }
    return cur;
}

int main() {
    
    cin >> n;
    
    for(int i=0;i<n;i++) {
        cin >> stone[i];
    }
    
    cout << go(0) << endl;
}