(BOJ 12008 262144) 이게 DP? 이게 Sparse table? (패턴)

그냥 봐선 이게 DP인지 싶음. 

그러나 뭔가 완전탐색 같은 방식은 N이 너무 커서 불가능 할 것 같고.

 

 

해답 코드가 있었는데, 주석이 하나도 없어서 그냥 봐선 이해가 힘들었다.

→ 무조건 손으로 직접 풀어보기. 손으로 풀고 시각화 하다보면 패턴이 보다 쉽게 찾아진다! 

그냥 봐서는 도저히 모르겠다 → 무조건 직접 써봐라/그려봐라. 패턴 보이기 시작할 것

 

어느 정도 패턴 파악한 뒤, 예제 손으로 돌려보며 완벽히 이해. 이후 pseudo-code 작성해서 DP 디자인 마무리

 

 

해석 후 다시 스스로 짜본 코드

D[i][num] : i번째에 num이 올 수 있는가? 만약 i~j번째 수를 합쳐서 num을 만들 수 있다면, j+1를 반환
(아니면 default 0)

 

점화식은, D[i][num]과, 이거 바로 뒤에 나타나는 똑같은 num이 있을 시 합쳐서 num+1을 만드는 과정에서 세워짐

(아래 왼쪽 그림 - TC 손으로 풀어보며 점화식 파악)

const int MAXN = 262145, MAXX = 61;
int D[MAXN][MAXX];

void solve() {
    int N, num;
    cin >> N;
    FOReq(i, 1, N) {
        cin >> num;
        D[i][num] = i;
    }

    int ans = 0;
    FOR(num, 1, 60) FOReq(i, 1, N) {
        int last_idx = D[i][num];
        if (last_idx > 0) {
            ans = num;
            if (last_idx < N) D[i][num + 1] = D[last_idx + 1][num];
        }
    }

    cout << ans;
}

 

 

---

Sparse table 풀이

혼자서라면 지금 레벨론 절대 찾지 못했을 듯.

https://justicehui.github.io/usaco/2020/03/11/BOJ12008/

백준12008 262144