ABC 419 - E : 정답 수열의 성질을 파악해 전처리 후 DP로 푸는 문제

https://atcoder.jp/contests/abc419/tasks/abc419_e

E - Subarray Sum Divisibility

 

회고

이번 ABC는 ABCDEFG 모든 문제의 지문이 짧아서 문제를 금방 이해하고 풀이에 돌입할 수 있었다.

특히 ABCD번 문제는 정말 쉬웠다. 32분만에 ABCD번 문제를 다 풀었는데도 3380등을 한 걸 보면 얼마나 쉬웠는지 알 수 있다

근데 E번 문제는 이것저것 풀이를 생각해볼 수 있으나 그것이 실제로 작동하는 아이디어인지 판단하기가 어려웠다

 

문제 지문

처음 아이디어

처음 문제를 봤을 땐 길이가 M으로 고정된 수열들의 조건을 맞춰주는 문제니깐. 슬라이딩 윈도우를 이용해 스위핑하면서 어떤 자료구조를 이용하면 정답을 구할 수 있겠다고 생각했는데. 스위핑 문제라기엔 N,M,L의 제한이 500이하로 매우 작았다

그래서....세제곱으로 돌아가는 플로이드를 의심하고 문제상황을 그래프로 가져올 수 있는지 판단했는데 될 리가 없었고 30분 이상 고민해도 답이 안나와서 문제를 던졌다

 

업솔빙

대회 종료 이후 DP로 풀린다는 얘기를 듣고 문제를 살펴봐도 도저히 모르겠음

그래서 에디토리얼을 봤다

https://atcoder.jp/contests/abc419/editorial/13672

Editorial - AtCoder Beginner Contest 419

 

일단 관찰을 통해 얻을 수 있는 핵심 아이디어는 이렇다고 한다. 나는 알아차리지 못했던 아이디어인데

첫번째 아이디어는 뭐 문제에 써져있던대로. 1부터 L까지 더한 값이 M의 배수여야 한다는 거고

두번째 아이디어는(핵심) L만큼 떨어진 원소들의 모듈로값이 모두 같아야 한다는 것이다.

이러한 아이디어는 정답수열에 슬라이딩윈도우를 적용했을 때 추가되는 값과 제거되는 값의 모듈러가 같아야 할 것이라는 관찰에서 얻을 수 있다

즉 L만큼 떨어진 원소들의 모듈러값을 같게 하는 계산을 전처리를 통해 미리 처리하는게 이 문제의 핵심이었던 것이다

 

그래서 여기까지 아이디어를 얻고 다시 풀이에 도전

//정답 코드
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int, int>
// #define int ll
using namespace std;
//ABC 419-E upsolve (2d later)

int N,M,L;
int arr[500];
int pre[500][500];//전처리될 배열
int dp[500][500];

int main()
{
    fastio;
    cin>>N>>M>>L; // <=500
    for (int i = 0; i < N; i++)
    {
        cin>>arr[i];
    }

    //전처리
    for (int st = 0; st < L; st++)
    {
        for (int modval = 0; modval < M; modval++)//통일할 나머지값
        {
            for (int i = st; i < N; i+=L)
            {
                int calc = modval-arr[i];
                if(calc<0)calc+=M;
                pre[st][modval]+=calc;
            }
        }
    }

    //0~L-1번 원소에 대해 전체 합이 M의 배수가 되도록 하기
    //이걸 dp로 계산하려면?

    memset(dp,0x3f3f3f3f,sizeof(dp));
    for (int i = 0; i < M; i++)
    {
        dp[0][i]=pre[0][i];
    }
    
    for (int i = 1; i < L; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int k = 0; k < M; k++)
            {
                int calc = j-k;
                if(calc<0)calc+=M;
                dp[i][j]=min(dp[i][j],dp[i-1][k]+pre[i][calc]);
            }
        }
    }
    cout<<dp[L-1][0];

    return 0;
}
//정답 코드

L*M*M의 시간복잡도로 풀렸다!!

 

뭘 배웠나요??

문제 조건을 아무리 관찰해도 아이디어를 얻을 수 없다면, 정답수열의 형태가 어떻게 될지를 추측해보는 게 도움이 된다는 것이다

 

그렇기에 이 문제의 경우도 예제를 보고 정답을 얻기 위해 어떤 절차를 거치게 되냐~ 하는 접근에 실패했다면

정답수열의 모양은 어떻게 될 것이고 그녀석의 성질은 어떠한가~ 하는 관찰을 했어야 하는 것이다

 

사실 원하는 배열의 모양을 상상하고 그걸 얻기 위해 전처리를 가하는 알고리즘을 우리는 이미 배웠다

누적합이나 imos법(차분 배열 트릭) 이 그렇다. 원하는 정답을 얻어내기 위한 배열의 모양을 상상하고 그 상상한 모양을 만들기 위한 전처리를 하게 된다는 점에서 이 문제와 비슷한 접근인 것 같기도 하다. 아님 말고

 

평가

나는 이런식으로 내가 생각 못한 아이디어가 적용되었을 때 쉽게 풀리는 문제들에 대해 재미를 느끼고 좋은 문제라고 평가한다

그렇기 때문에 이 문제 역시 좋은 문제라는 생각이 들고 기억에 남을 것 같다

 

다만 에디토리얼에 첨부된 O(NM)풀이는 이해가 다소 어렵다

Google To-Do에 O(NM)풀이를 예정된 할일로 추가해놓고 3일 후에 다시 풀어봐야겠다