[백준] No.7570 - 줄 세우기 (C++)

문제

https://www.acmicpc.net/problem/7570

7570번: 줄 세우기

 

풀이

 

solved.ac 난이도: Gold 4

 

탐욕법과 동적계획법을 이용해야하기 때문에 까다로웠던 문제이다.

풀이는 마이구미님의 게시글을 참고하였다.

 

문제를 풀기 전에, 이전 단계 문제라고 볼 수 있는 백준 - 줄 세우기(2631)을 함께 풀어보면 좋다.

 

2631번 줄 세우기 문제에 사용되는 동적계획법의 알고리즘은 LIS(최장 증가 부분 수열)이다.

해당 문제는 어느 위치로든 이동시킬 수 있으므로 LIS로 선택된 수 이외의 수 이외의 각각 한 번씩만 움직여서 해결할 수 있다.

 

예를 들어 아래의 예제에서는 LIS의 길이는 3이다.

1 4 3 2 5

이를 순서대로 바꿀려면 3과 2를 한 번씩만 이동시키면 충분하다.

 

하지만 7570번 줄 세우기 문제는 맨 앞이나 뒤로만 이동 가능하기 때문에 단순히 증가하는 부분 수열을 선택하면 해결이 불가능하다.

1 4 3 2 5 -> 2와 3의 이동으로는 정렬이 불가능

 

따라서 7570번은 연속된 수의 최장 증가 부분 수열을 구해야 한다.

2 1 3 5 4 6 과 같은 예시를 생각해보자.

 

해당 예시에서는 2,3,4가 연속된 최장 증가 부분 수열이다.

연속된 3개의 수 이외의 수만 이동시켜 주면 정렬이 가능하기 때문에 연속된 수는 맨 앞이나 맨 뒤로 이동할 이유가 전혀 없다.

따라서 나머지 수를 각각 한 번씩만 이동시켜주면 해결이 가능하다. 

ex) 1 2 3 5 4 6 -> 1 2 3 4 6 5 -> 1 2 3 4 5 6

 

이제 풀이를 코드로 구현해보자. 

LIS를 그대로 가져와서 구현하면 편하겠지만 지나온 수들을 모두 확인하는 알고리즘(위의 LIS 링크 참조)은 O(N^2)의 시간 복잡도를 가지기 때문에 최대 입력 크기인 1,000,000을 시간 안에 탐색할 수 없다.

 

따라서 해당 번호가 어느 위치에 저장되었는지 바로 찾을 수 있도록 아래와 같이 입력을 받아준다.

 

for(int i=0; i<children_num ; ++i){
    cin>>idx_to_num[i];                //idx_to_num에는 줄을 서있는 순서를 저장
   num_to_idx[idx_to_num[i]] = i;    //num_to_idx에는 각 번호를 가진 아이가 있는 위치를 저장
}

num_to_idx[num]에는 num의 번호가  idx_to_num에 저장된 위치(idx)가 저장된다.

그렇다면 idx의 위치에서부터 시작하는 연속된 증가수열을 구하기 위해서는 idx_to_num[idx](idx위치에 서있는 아이의 번호)에 +1을 한 값이 idx의 위치보다 큰지 확인해야 한다.

만약 다음 값이 idx보다 이후에 존재한다면 해당 값이 가지고 있는 연속된 증가수열 길이 값(sequence_cache[num_to_idx[idx_to_num[idx]+1]])을 그대로 가져와 +1을 한 것이 sequence_cache[idx]의 값이다.

 

sequence_cache[idx] = sequence_cache[num_to_idx[idx_to_num[idx]+1]] +1

 

최종적으로 sequence_cache중에서 가장 큰 값을 아이들의 수(N, children_num)에서 빼주면 최소 이동 개수가 된다.

children_num - max_sequence_len

 

변수명이 너무 복잡해서 잘 이해가 되지 않는다면 마이구미님이 소개한 더 빠르고 간결한 코드도 있다.

 

int cache[1000001];
int num,max_sequence_len=1;
 
memset(cache, 0 , sizeof(cache));
 
for(int i=0; i<children_num ; ++i){
  cin>>num;
  cache[num] = cache[num-1]+1;    
  max_sequence_len = max(max_sequence_len, cache[num]);
}

cache[num -1]가 0이라면 이전 값이 먼저 나오지 않았다는 뜻이다.

따라서 해당 num부터 처음 시작하는 연속 증가수열의 길이인 1을 cache[num]에 저장한다.

 

cache[num -1]가 0이 아니라면 ...num-1 -> num가 이어지는 연속 증가 수열이 존재한다는 의미이다.

따라서 cache[num] = cache[num-1]+1이 num까지 이어지는 수열의 길이이다.

 

이중에서의 최댓값이 최장 연속 증가수열의 길이이다.

코드