[도전 3일차] 막대기, 섞기 수열

문제 1: BOJ 8984 막대기

문제 링크:KOI 2013 고등부 2번

 

사용 알고리즘 : DP 다이나믹 프로그래밍

 

풀이: 

출처 : 백준

막대기들 중에서 지그재그 형식으로 이어진 선을 찾자. 지그재그 선들 중에서 최대의 길이를 찾는 것이 목표다.

지그재그란 : a-b-e, c-d-f-g 와 같이 서로 이어지면서 교차하지 않는 선을 말한다. 특히 한 점에서 3개 이상의 선이 만날 수 없다. 

선의 길이란: 수평거리 + 수직거리 = 절대값( 시작점 x좌표 - 끝점 x좌표) + L 을 의미한다.

 

먼저 좌표들을 높이로 Top , Down으로 분리하자.

그리고 좌표들을 Top 오름차순으로 정렬한 후 unique( v.begin(),v.end() ) 를 이용해 겹치는 것들을 제거한다. 

 

Top ,Down 에서 따로 DP를 정의할 건데, Top을 기준으로 정의하자면

DP [ id ] = Top 에 있는 id 번째 점을 마지막으로 하는 지그재그 선 길이의 최대값.

 

그럼 이제 DP 테이블을 채워보자. 사실 좌표들을 분리하기 전에 선들도 입력받아서 저장해야 한다.

vector<pair<int,int>> 형식으로 저장했다고 하자. sort 를 때려서 선들 간 순서를 만들자.

이렇게 해도 되는 이유는 Top을 기준으로 생각했을 때 Top에 있는 점으로 끝나는 지그재그 길이의 최대값을 구하려면

그 점 이전에 있는 지그재그 선의 길이를 구할 수 있어야 한다. 그런데 그 전에 있는 지그재그 선의 시작값은, 그 점의 Top 좌표보다 작을 수 밖에 없으므로 Top을 기준으로 정렬해도 된다.

 

마찬가지로 Down을 기준으로 생각했을 때도 DT를 채우려면 그 전 값의 DT[top] 값이 필요하다. (선은 Top과 Down을 연결한 형태이므로) 그렇기 때문에 Top 오름차순, 같으면 Down 오름차순으로 정렬하면 DT 테이블을 채울 순서가 완성된다.

 

이제 선들을 순서대로 살펴보자. 아까 좌표들을 압축해놓았던거 기억하는가? lower_bound를 이용해 이 좌표가 몇번째 Top/Down 좌표인지 구하자. 그것을 각각 t_id, d_id 라 하자.

그 다음 DT 값을 갱신해주는데 Top을 마지막으로 하는 DT 를 T_DT, Down을 마지막으로 하는 DT를 D_DT라고 하자.

선의 길이를 len = abs(pair.first-pair.second)+L; 라 하자. 

 

DT 갱신 관계식은 다음과 같다.

let t=T_DT[t_id],d=D_DT[d_id];
T_DT[t_id]=max(t,d+len);  D_DT[d_id]=max(d,t+len);

선을 기준으로 살펴보는 것이므로 Top을 마지막으로 끝나는 지그재그 선의 최대값을 갱신할 때는, 선의 맞은편 Down을 마지막으로 끝나는 (이전까지의) D_DT[id] + len으로 갱신이 가능하다. 이때 최대값을 구하는 것이므로 max function을 이용해 갱신할지 말지 결정하면 된다.

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
int n,L;
vector<pair<int,int>> line;
vector<int> T,D;
long long T_DT[100010],D_DT[100010];
// idx 로 끝날 때, 지그재그 선 길이의 최대값 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>L;
    for(int i=0,a,b;i<n;i++){
        cin>>a>>b;
        line.emplace_back(a,b);
        T.push_back(a); D.push_back(b);
    }
    vsort(line); vsort(T); vsort(D);
    T.resize(unique(T.begin(),T.end())-T.begin());
    D.resize(unique(D.begin(),D.end())-D.begin());
    for(auto& p:line){
        int len=abs(p.first-p.second)+L;
        int t_id=lower_bound(T.begin(),T.end(),p.first)-T.begin();
        int d_id=lower_bound(D.begin(),D.end(),p.second)-D.begin();
        long long t=T_DT[t_id],d=D_DT[d_id];
        T_DT[t_id]=max(t,d+len);
        D_DT[d_id]=max(d,t+len);
    }
    cout<<max(*max_element(T_DT,T_DT+n),*max_element(D_DT,D_DT+n));
}

문제 2: BOJ 2487 섞기 수열

문제 링크

 

사용 알고리즘 : 최소공배수, 사이클 탐색

 

풀이: 

쉽게 알 수 있지만 섞기 수열은 1~n을 재배열 한 것이다.

이 때 기존 수열을 정의역, 섞은 후의 수열을 치역이라고 하면 섞기 수열은 일대일대응 함수가 된다.

예를 들어 [1,2,3,5,4] 라는 섞기 수열이 있다면

1 2 3 4 5 를 섞으면

1 2 3 5 4가 되고, 다시 섞으면

1 2 3 4 5 가 되어 2번만에 제자리로 되돌아 온다.

이때 같은 자리에 있는 아이들끼리만 자리가 변하는 것을 관찰할 수 있다.

즉, 섞기 수열에서 사이클을 찾으면 된다. 사이클을 찾는 방법은 다음과 같다.

for(int i=1;i<=n;i++){
	if(!chk[i]){
		int k=i,cnt=0;
		do{
			chk[k]=1;
			k=arr[k];
			cnt++;
		}while(k!=i);
		cycle.push_back(cnt);
	}
}

chk 는 i가 사이클에 속해 있는지 확인해주는 배열이다.

cnt는 사이클의 길이를 뜻한다.

 

사이클의 배수번 섞으면 제자리로 돌아오므로, 전체 사이클들의 최소공배수를 구해주면 된다.

A,B의 최소공배수를 구하는 방법은 다음과 같다. 최대공약수를 G라고 두고,

A=G * a, B=G * b 라 하자. 그러면 a와 b는 서로소이므로 최소공배수는 G * a * b = A * B /G 임을 알 수 있다.

아래와 같은 방법으로 

int ans=cycle[0],g;
for(int i=1;i<cycle.size();i++){
	g=gcd(ans,cycle[i]);
	ans=ans/g*cycle[i];
}
cout<<ans;

최소공배수를 구해주자.

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
int n,arr[20001],chk[20001];
vector<int> cycle;
int gcd(int a,int b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++){
        if(!chk[i]){
            int k=i,cnt=0;
            do{
                chk[k]=1;
                k=arr[k];
                cnt++;
            }while(k!=i);
            cycle.push_back(cnt);
        }
    }
    int ans=cycle[0],g;
    for(int i=1;i<cycle.size();i++){
        g=gcd(ans,cycle[i]);
        ans=ans/g*cycle[i];
    }
    cout<<ans;
}