어떤 문제인가?

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

시행착오 횟수

4번

관찰

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

1차 시도 : WA

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

$\text{MLN}_{n}$

1. $\text{MLN}_{n} > P_{n}$

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

2. $\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}$

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

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); 
}

dnltjd770님의 소스
-> https://www.acmicpc.net/source/30814941

내 첫번째 방식과 유사하나, 내가 놓친 부분이 있었기에 나는 틀리고 이분은 맞았을 것이다. 시간이 날 때 해당 코드를 한번 분석해봐야겠다.

한줄평

거의 다 온 것 같은데 막히니까 매우 짜증났다. 결국에는 풀었지만 한동안 이 문제에 대한 풀이 후기를 쓸 생각을 안했을 정도면 얼마나 짜증이 났을지 짐작이 간다.