스택활용하기, 꼬리잡기

문제

꼬리잡기 게임을 한다. 일직선 상에서 진행하며 모두 동시에 출발하지만

출발 위치와 속도는 다르다. T분동안 게임이 진행되며 일직선 상이기 때문에 추월할 수 없고

속도가 빠른 뒷사람의 앞사람의 꼬리를 잡으면 하나의 그룹으로 인식된다.

주어진 조건에서 몇개의 그룹이 형성되는지 구하라

 

입력

참가자 수 N : 1~100,000

게임시간 T : 1~1,000,000,000

각 참가자출발 위치 P : 0 ~ 1,000,000,000

각 참가자 속도 S : 0 ~ 1,000,000,000

 

※ 출발위치는 오름차순으로 입력됨

 

5 3

0 1

1 2

2 3

3 2

6 1

 

출력

3

---

접근방식

아주 간단하게 생각해보자.

1. 각 참가자의 계산된 T분 후 위치를 구한다.2. 뒷 사람이 앞사람보다 위치가 클 경우, 앞사람의 위치로 보정한다.   단, 추월이 불가하므로 맨 마지막 참가자가 가장 선두이므로 역으로 보정을 수행한다.3. 그룹의 총 개수를 구한다.

 

표로 표현하면 아래와 같을 것이다.

이때 보정을 정방향으로 수행하게 되면 완전한 보정을 보장하지 못하며 비효율적이다. 0번 참가자가 9, 1번이 8, 2번이 3일 경우 정방향으로 보정하게 되면 0번 참가자를 8로 보정 하고 1번을 3으로 보정하고 다시 0번을 3으로 보정해야 하기 때문이다.

 

추월을 하지 못하므로 가장 마지막 참가자를 기준으로 역으로 보정하면 O(N)에 끝낼 수 있다.

 

코드는 아래와 같다.

#include <stdio.h>

int N;
long long T;
long long P[110000]; //위치
long long S[110000]; //속도

void Input(){
	scanf("%d %d", &N, &T);
	for(int i=0; i<N; i++){
		scanf("%d %d", &P[i], &S[i]);
	}
}

void Calc(){
	 for(int i=0; i<N; i++){
		 P[i] = P[i] + S[i]*T;
	 }
}
int main() {
	Input();
	Calc();
	
	for(int i=N-1; i>=1; i--){
		//printf("%d ",P[i]);
		if(P[i]<P[i-1]) P[i-1]=P[i];
	}
	
	int ans = 1;
	for(int i=0; i<N-1; i++)
	{
		if(P[i] != P[i+1]){
			ans++;
		}
	}
	
	printf("%d", ans);
	
	return 0;
}

---

역방향 말고 정방향으로는 방법이 없을까? 스택을 활용하여 생각해보자.

그룹의 선두만 기억하는 것이다.

1. 첫 참가자는 Stack에 바로 Push

2. 다음참가자가 Stack보다 크면 Push

3. 다음 참가자가 Stack보다 작거나 같으면 Pop : Stack 전체를 반복

4. 3번 후 Push

 

코드는 아래와 같다.

#include <stdio.h>

int N;
long long T;
long long P[110000]; //위치
long long S[110000]; //속도
int sp=0;
long long stack[110000];


void Input(){
	scanf("%d %d", &N, &T);
	for(int i=0; i<N; i++){
		scanf("%d %d", &P[i], &S[i]);
	}
}

void Calc(){
	 for(int i=0; i<N; i++){
		 P[i] = P[i] + S[i]*T;
	 }
}

void Stack(){
	for(int i=0; i<N; i++)
	{
		for(; (sp>0) && (stack[sp] >= P[i]); sp--);
		stack[++sp] = P[i];
	}

	/*
	stack[++sp]=P[0]; //sp 1에 넣기
	for(int i=1; i<=N-1; i++){
		//printf("%d, stack %d\n", sp, stack[sp]);
		if(P[i]>stack[sp]){
			//push
			stack[++sp]=P[i];
		}
		
		else{
			for(int j=sp; j>=0 && stack[sp] >= P[i]; j--)
			{
				sp--;	
			}
			stack[++sp]=P[i];
		}
	}
	*/
	
}

void Print(){
	for(int i=0; i<=sp; i++)
		printf("sp<>%d : %d ",sp, stack[i]);
	printf("%d\n");
}

int main() {
	Input();
	Calc();
	Stack();
	printf("%d", sp);
	
	return 0;
}