[프로그래머스] 2023 현대모비스 알고리즘 경진대회 예선 문제 풀이

5/29부터 2024 현대모비스 알고리즘 경진대회 접수가 시작되었습니다.

작년에 참여했을 때 예선에서 2문제를 풀고 광탈했었는데, 이번에 예선 때 못 풀었던 문제까지 도전해볼 겸 연습 삼아 다시 풀어보았습니다.
(작년 예선/본선 기출문제들은 여기에서 보실 수 있습니다.)

개인적으로, 예선치고는 문제가 아주 어렵다고 느꼈습니다...

---

1. 상담원 인원

$n \leq 20, k \leq 5$이고 '각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.'라는 조건이 있으므로, 각 유형에 멘토를 배정하는 모든 경우의 수는 $n=20, k=5$인 경우 $_{20-5}H_{5} = _{15+5-1}C _{5} = _{19}C_{5}$ = 11,628가지로 그렇게 많지 않습니다. (n이나 k가 이보다 작다면 경우의 수는 더 적어집니다.)

따라서 유형별 멘토의 수를 고정해두고 모든 경우에 대해 시뮬레이션하면 됩니다.
-> (v[x]: x번 유형의 멘토 수)라고 정의된 배열 v를 백트래킹으로 채웁니다.

참가자가 상담 x를 요청했을 때, x번 유형의 멘토들 중 이전 상담이 가장 먼저 끝난 멘토가 해당 참가자에게 배정되어야 하므로 priority_queue를 사용합니다. (맨 처음엔 pq[x]에 0분에 상담을 마친 멘토를 v[x]명 넣어놓습니다.)

시간복잡도는 배열 v를 채우는 데 $_nC_k$, 최대 길이 n의 pq를 사용하므로 $log_{2}(n)$, 시뮬레이션할 때 $len(reqs)$만큼 탐색하므로 $O(_nC_k * len(reqs) * log(n))$ 입니다.

코드

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> reqs;
int k,ans;
void go(vector<int> &v,int n){
    if(v.size()==k){
        int w=0;
        priority_queue<int,vector<int>,greater<int>> pq[6];
        for(int i=0;i<k;i++)for(int j=0;j<v[i];j++)pq[i+1].push(0);
        for(auto x:reqs){
            int a=x[0],b=x[1],c=x[2];
            auto p=pq[c].top();pq[c].pop();
            w+=max(0,p-a);
            pq[c].push(max(a,p)+b);
        }
        ans=min(ans,w);
        return;
    }
    for(int i=1;i<=n;i++){
        v.push_back(i);
        go(v,n-i);
        v.pop_back();
    }
}
 
 
int solution(int kk, int n, vector<vector<int>> r) {
    reqs=r,k=kk,ans=2e9;
    vector<int> v;
    go(v,n);
    return ans;
}

---

2. 에어컨

우선 -10도까지 배열의 인덱스로 사용하기 위해, 모든 온도에 10을 더해줍시다.

dp[x][y]: (x-10)도, y분일 때의 최소 비용으로 정의합니다.

나머지 구현은... 문제의 설명을 그대로 코드로 옮기면 됩니다.

시간복잡도는 $O(50*len(onboard))$입니다. 

코드

#include<bits/stdc++.h>
using namespace std;
 
int dp[51][1001];
 
int solution(int temperature, int t1, int t2, int a, int b, vector<int> onboard) {
    int n=onboard.size();
    t1+=10,t2+=10,temperature+=10;
    memset(dp,0x3f,sizeof(dp));
    dp[temperature][0]=0;
    for(int i=0;i<n-1;i++){//현재 i분, i+1분으로 넘어감.
        for(int t=0;t<=50;t++){//현재 t도,nt도로 넘어감.
            int nt=t;
            //에어컨 껐음(0원 소모)
            if(temperature<t)nt--;else if(temperature>t)nt++;
            if(!(onboard[i+1]&&(nt<t1||t2<nt)))//이상한 경우가 아니라면,
                dp[nt][i+1]=min(dp[nt][i+1],dp[t][i]);
            //희망온도 설정했음(a or b원 소모)
            for(int d=-1;d<=1;d++){
                nt=t+d;if(nt<0||nt>50)continue;
                int add=!d?b:a;
                if(!(onboard[i+1]&&(nt<t1||t2<nt)))//이상한 경우가 아니라면,
                    dp[nt][i+1]=min(dp[nt][i+1],dp[t][i]+add);
            }
        }
    }
    int answer = 1e9;
    for(int t=0;t<=50;t++)answer=min(answer,dp[t][n-1]);
    return answer;
}

---

3. 경사로의 개수

먼저, 무조건 k=1이라고 가정하고 답을 구해봅시다.

arr[x1][y1][x2][y2][z]: (x1,y1)에서 시작해서 경사 수열의 d[z]인 길까지 이동했을 때, (x2,y2)에 도착하는 경우의 수라고 정의합시다.
이 배열은 $O((nm)^2*len(d))$에 모두 채울 수 있고, k=1일 때 답은 $\sum\limits_{i_1=0}^{n-1}\sum\limits_{j_1=0}^{m-1}\sum\limits_{i_2=0}^{n-1}\sum\limits_{j_2=0}^{m-1} arr[i_1][j_1][i_2][j_2][len(d)-1]$가 됩니다.

배열의 인덱스가 너무 많아서 헷갈립니다... 코드를 짜기 전에 표현 방식을 이렇게 바꿔봅시다.

• (x1,y1)을 (x1*m+y1)으로 묶어 S로 표현
• (x2,y2)를 (x2*m+y2)로 묶어 E로 표현
• dp 토글링을 사용하여, arr[S][E][i]를 v[E], arr[S][E][i+1]을 nv[E]에 저장하면서 값을 채워나감.
• 최종적으로, 위 설명에서의 arr[x1][y1][x2][y2][len(d)-1]를 아래 코드에서 a[S][E]로 표현.
  (k=1일 때, 답은 $\sum\limits_{s=0}^{nm-1}\sum\limits_{e=0}^{nm-1} a[s][e]$가 됩니다.)

이제 k=1일 때의 답을 구했으니, k=2일 때의 답도 구해봅시다.

이 값은 배열 a에서 찾을 수 있는데, 예를 들어 경사 수열을 2번 반복하여 S -> E로 가는 경우의 수는 $\sum\limits_{i=0}^{nm-1} a[S][i] * a[i][E]$가 됩니다. (경사 수열을 1번 반복해서 S -> i에 도착했고, 다시 1번 반복해서 i -> E에 도착합니다.)

이 과정은 배열 a를 (nm)*(nm) 크기의 행렬로 생각하면, 행렬 곱셈으로 $O((nm)^3)$에 구할 수 있습니다.
그리고 배열을 k번 거듭제곱하는 과정은 분할정복을 이용하여 $log_2(k)$번 안에 구할 수 있습니다.

따라서 시간복잡도는 $O((nm)^2*len(d) + (nm)^3*log(k))$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<vector<ll>> mat;
pii go[4]={{1,0},{-1,0},{0,1},{0,-1}};
const ll mod=1e9+7;
 
mat mul(mat a, mat b){
    //a:x*y행렬, b:y*z행렬 -> 결과 : x*z행렬. 여기서는 x==y==z.
    mat ret(a.size(),vector<ll>(b[0].size()));
    for(int x=0;x<a.size();x++)for(int z=0;z<b[0].size();z++){
        ll val=0;
        for(ll y=0;y<b.size();y++)val+=a[x][y]*b[y][z]%mod;
        ret[x][z]=val%mod;
    }
    return ret;
}
 
mat power(mat a, ll d){
    int nm=a.size();
    mat ret(nm,vector<ll>(nm));
    for(int i=0;i<nm;i++)ret[i][i]=1;
    while(d){
        if(d%2)ret=mul(ret,a);
        a=mul(a,a);
        d/=2;
    }
    return ret;
}
 
int solution(vector<vector<int>> grid, vector<int> d, int k) {
    int n=grid.size(),m=grid[0].size();
    //matrix a: x에서 시작해서, 경사수열을 1번 완주하고 y에 도착하는 경우의수.
    mat a(n*m,vector<ll>(n*m));
    
    for(int S=0;S<n*m;S++){
        vector<ll> v(n*m);v[S]=1;
        for(auto s:d){
            vector<ll> nv(n*m);
            for(int i=0;i<n*m;i++){
                int x=i/m,y=i%m;
                for(auto [dx,dy]:go){
                    int nx=x+dx,ny=y+dy;
                    if(nx<0||nx>=n||ny<0||ny>=m||grid[nx][ny]-grid[x][y]!=s)continue;
                    nv[nx*m+ny]=(nv[nx*m+ny]+v[i])%mod;
                }
            }
            v=nv;
        }
        for(int E=0;E<n*m;E++)a[S][E]=v[E];
    }
    mat result=power(a,k);
    ll ans=0;
    for(int i=0;i<n*m;i++)for(int j=0;j<n*m;j++)ans+=result[i][j];
    return ans%mod;
}

---

4. 집합과 쿼리

1번 쿼리만 있다고 가정하면 유니온 파인드로 쉽게 답을 구할 수 있었겠지만, 2번 쿼리 때문에 집합마다 집합에 포함된 모든 정수와 집합에 들어온 순서를 기록해두어야 합니다.

그런데, 만약 매번 집합의 원소들을 직접 모두 옮긴다면 $O(len(queries)*n)$의 시간이 걸려 시간초과를 받게 됩니다.

여기서 한 가지 중요한 관찰을 해야 하는데, 1번 쿼리 [1, x, y]에서, 집합 y에 포함된 원소들은 앞으로 쿼리 순서가 계속 같으면서 같은 집합에 속합니다. 마찬가지로 2번 쿼리 [2, x, y]에서, 새로 생성한 집합으로 옮겨지는 원소들 또한 앞으로 쿼리 순서가 계속 같으면서 같은 집합에 속합니다. 따라서 이 원소들은 앞으로 다른 집합으로 분리될 수 없고, 그냥 하나의 원소로 취급해도 됩니다.(유니온 파인드를 이용해서, 옮겨질 원소들을 하나로 묶어줍시다.)
결과적으로,
1번 쿼리를 수행하면 집합의 크기가 [집합 x: len(x) / 집합 y: len(y)]에서 [집합 x: len(x)+1 / 집합 y: 0]이 되고,
2번 쿼리를 수행하면 집합의 크기가 [기존 집합: len(x) / 새로운 집합: 0]에서 [기존 집합: len(x)-옮겨질 원소 개수 / 새로운 집합: 1(옮겨질 원소가 없다면 0)]가 되는 것입니다.

따라서 1, 2번 쿼리들을 총 $O(n+len(queries))$에 모두 수행할 수 있는데, 제 코드는 2번 쿼리에서 순서 [x~y] 사이에 들어온 원소들의 구간을 이분 탐색으로 찾고, 각 원소의 삭제 연산(기존 집합에서 새로운 집합으로 옮김)을 수행하기 위해 map 자료구조를 사용해서 $log_2(n)$의 시간이 추가로 붙었고, 최종적으로 시간복잡도는 $O(log(n)*(n+len(queries)))$이 되었습니다. (만약 매 2번 쿼리마다 기존 집합의 모든 쿼리 순서를 탐색하면 여전히 $O(len(queries)*n)$의 시간복잡도가 되어 시간초과를 받을 것입니다.)

코드에 사용된 변수들의 뜻은 다음과 같습니다.

• qnum[i]: 정수 i가 어떤 집합에 들어온 순서
• snum[i]: 정수 i가 포함된 집합의 번호
• ith: 현재 쿼리의 순서를 나타내는 번호
• new_setnum: 2번 쿼리에 의해 새로 생성된 집합의 번호
• v[i]: i번 집합에 포함된 {쿼리 순서, 정수}목록.
• M: 쿼리에 의해 옮겨질 원소들의 목록

코드

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int u[500000],qnum[500001],snum[1000001],ith,new_setnum;
map<int,int> v[1000001];//i번 집합에 포함된 {쿼리순서,정수}.
int find(int x){return u[x]<0?x:u[x]=find(u[x]);}
bool merge(int a,int b){
    a=find(a),b=find(b);
    if(a==b)return false;
    u[a]+=u[b],u[b]=a;
    return true;
}
 
void init(int n){
    ith=0,new_setnum=n-1;
    for(int i=0;i<n;i++)v[i][ith]=i,snum[i]=i,u[i]=-1;
}
 
vector<string> solution(int n, vector<vector<int>> queries) {
    init(n);
    vector<string> answer;
    for(auto Q:queries){
        int q=Q[0],x=Q[1],y=Q[2];
        ith++,x=find(x),y=find(y);
        int sx=snum[x],sy=snum[y];
        if(q==1){
            if(sx==sy)continue;
            //y들은 이제부터 무조건 같은 집합에 속하므로, 묶어서 하나의 정수로 취급한다.
            vector<int> M;
            for(auto [a,b]:v[sy])qnum[b]=ith,snum[b]=sx,M.push_back(b);
            for(int i=1;i<M.size();i++)merge(M[i-1],M[i]);
            v[sy].clear(),v[sx][qnum[M[0]]]=M[0];
        }
        else if(q==2){
            vector<int> M;
            //쿼리 순서가 [l~r]인 원소들을 새로운 집합에 옮긴다.
            ++new_setnum;
            int l=qnum[x],r=qnum[y];
            auto it=v[sx].lower_bound(l);
            while(it!=v[sx].end()&&it->first<=r){
                int a=it->first,b=it->second;
                qnum[b]=ith,snum[b]=new_setnum,M.push_back(b);
                it=v[sx].erase(it);
            }
            //M들은 이제부터 무조건 같은 집합에 속하므로, 묶어서 하나의 정수로 취급한다.
            for(int i=1;i<M.size();i++)merge(M[i-1],M[i]);
            if(!M.empty())v[snum[M[0]]][qnum[M[0]]]=M[0];
        }
        else{
            if(snum[x]==snum[y])answer.push_back("Yes");
            else answer.push_back("No");
        }
    }
    return answer;
}

---

+) 참고용으로 각 코드의 실제 동작시간을 첨부했습니다.

1, 2, 3, 4번 코드 동작시간 / 메모리