1021 : 회전하는 큐

네르기·2021년 9월 5일

덱 분석 필요 생각

알고리즘

목록 보기

44/76

어떤 문제인가?

덱을 이용, 문제에서 언급된 2가지 연산을 사용한 횟수의 최솟값을 구하는 문제.

시행착오 횟수

4번

관찰

2번째와 3번째 연산 중 어떤 연산을 최소 횟수로 할 수 있는지 확인하기 위해서는 어떤 원소와 목표 원소 간 좌, 우측 거리를 비교해야 한다.
1번째 연산으로 사라진 원소는 거리 계산에 포함하면 안된다.

1차 시도 : WA

덱을 쓰는 대신, 가장 좌측에 있는 수를 $\text{MLN}$ 이라고 정하고, 이를 기준으로 계산을 진행했다.

$\text{MLN}_{n}$ 과 목표 원소 $P_{n}$ 간 위치관계에 따라 좌•우측 거리는 다음과 같이 계산했다.
이때 $N$ 은 주어진 큐의 길이이다.

$\text{MLN}_{n} > P_{n}$
$L = \text{MLN}_{n}-1 + (N-P_{n}) \\ R = |P_{n}-\text{MLN}_{n}|$
$\text{MLN}_{n} < P_{n}$
$L = |\text{MLN}_{n} - P_{n}| \\ R = N-\text{MLN}_{n} + (P_{n}-1)$

이 방식은 관찰 2.를 무시하면 틀린다.
내 첫번째 코드는 이를 고려했지만, 삭제 연산을 처리하는 부분과 인덱스를 옮기는 코드가 잘못되어 틀렸다.

#include <stdio.h>

int main()
{
	int N,M,P,c=0,i,j,L,R,T=1,U[51]={1,0};
	scanf("%d%d",&N,&M);
	for(i=0;i<M;i++) {
		scanf("%d",&P);
		L=R=0;
		if(P>=T) {
			for(j=T+1>N?1:T+1;j<=P;j++)
					if(!U[j]) R++;
		    for(j=T-1;j!=P;j=j<=1?N:j-1)
			    if(!U[j]) L++;
			L++;
		} else {
			for(j=T-1;j>=P;j--)
			    if(!U[j]) L++;
			for(j=T+1>N?1:T+1;j!=P;j=j>=N?1:j+1)
			    if(!U[j]) R++;
			R++;
		}
		c=L>=R?c+R:c+L;
		U[P]=1;
		for(j=P+1>N?1:P+1;j!=P;j=j>=N?1:(j+1)) {
		    if(!U[j]) { T=j; break; }
		}
	}
	printf("%d",c);
}

2차 시도 : PE

깜빡하고 디버깅 정보 출력하는 줄을 안지웠다.

3차 시도 : WA

이때 밤 11시를 넘어가서 피곤했는지는 몰라도, Ad-Hoc 코드로 넘어가려고 했었다. 당연하지만 근본적인 문제가 해결되지 않았기에 틀렸다.

4차 시도 : 구상

어떤 $F_{n}$ 에 대해, $F_{n+1}$ 를 알아낼 방법을 떠올렸다.
$F_{n}$ 는 n번째 연산이 끝난 이후의 큐의 Front 인덱스, $P_{n}$ 는 목표 원소이다.

L_{n} = sign(F_{n}-P_{n})\times (F_{n}-P_{n}) \\ F_{n} = F_{n-1}+min(L_{n}, N-L_{n}) \\ sign(x) = \begin{cases} 1 & (x \geq 0) \\ -1 & (x < 0) \end{cases}

그럼 뭐하나. 제거된 원소를 여전히 고려하지 않고 있는데.

5차 시도 : AC

계산하는게 틀린다면 무식하게 하나씩 확인하는 것도 방법이다.

#include <stdio.h>

int Q[50],F=0,N,M,c=0;

int main()
{
	int P,d,i,t1,t2,k1,k2;
	scanf("%d%d",&N,&M);
    while(M>0) {
        t1=t2=0;
        scanf("%d",&P); P--;
        for(i=F;i!=P;i=(i+1)%N) {
        	if(Q[i]==0) t1++;
        } k1=i;
        for(i=F;i!=P;i=(i-1+N)%N) {
        	if(Q[i]==0) t2++;
        } k2=i;
        if(t1>t2) {
        	F=k2; c+=t2;
        } else {
        	F=k1; c+=t1;
        }
        Q[F]=1; M--;
        while(Q[F]==1 && M>0) { F=(F+1)%N; }
    }
    printf("%d",c);
}

계산 대신 $O(N)$ 탐색으로 직접 확인하고, 가장 횟수가 적은 쪽으로 Front 인덱스를 옮김과 동시에 총 횟수에 더했다.
또한 삭제 과정에서 Front 인덱스가 이미 삭제된 곳을 가리킬 수 있었기에, 큐에 실제로 존재하는 원소를 가리키도록 했다.

다른 분들의 풀이

#include <stdio.h>
int main() { 
    int n, m, s, c=1, t, ans=0;
    static char v[52]; 
    scanf("%d%d",&n,&m); 
    for(int r=0;r<m;r++) { 
        scanf("%d",&s); 
        for(t=0;c!=s;c=c%n+1) 
            t+=v[c]==0; 
        ans += (t<n-r-t)?t:n-r-t; 
        v[c]=1; 
    } 
    printf("%d\n", ans); 
}