[BOJ 20971] No Time to Paint

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

20971번: No Time to Paint

 

- 문제 요약

 

Bessie는 최근 선물 받은 물감 세트로 목초지 한쪽 끝에 있는 긴 울타리(1m짜리 판자가 이어진 형태)를 칠하려 합니다.

울타리의 길이는 N이며 Bessie는 26가지의 색상을 가지고 있습니다.

각 판자마다 'A'~'Z' 문자로 라벨링을 해줄 생각입니다. (어두운 순서대로, 'A'가 제일 밝은 색, 'Z'가 제일 어두운 색)

모든 울타리는 색이 칠해져 있지 않은 상태입니다. (칠할 때 울타리에 칠해진 색보다 어두운 색만 덧바를 수 있습니다.)

 

Bessie가 색을 칠하지 않고 비워둘 판자의 인덱스 범위를 Q개 알려줄 때, 인덱스 범위를 제외한 모든 울타리에 색을 채우기 위해 해야 하는 최소 터치 횟수를 구하시오.

 

 

- 알고리즘 정리

 

입력받는 범위를 (a, b)라고 했을 때, a-1~N-b 구간에서의 최소 터치 횟수를 계산해 주면 됩니다.
for 범위 내에서 스택의 top보다 더 어두운 색상이 보인다면 push, 더 밝은 색이 보인다면 pop 해주면 됩니다.
이때, 더 어두운 색상이 보인다는 건 붓터치 횟수가 1 증가했다는 의미로 받아들일 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
int n,q,arr[MAX],brr[MAX];
string s;

void f(int *x){
	stack<char>s;
	for(int i=0;i<n;i++){
		x[i+1]=x[i];
		while (!active_colors.empty() && active_colors.top() > S[i]) active_colors.pop();
    	if (active_colors.empty() || active_colors.top() < S[i]) { active_colors.push(S[i]); sol[i+1]++; }
		while(){
			
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>q>>s;
	f(arr);
	reverse(s.begin(),s.end());
	f(brr);
	for(int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		cout<<arr[a-1]+brr[n-b]<<'\n';
	}
}

코드 제출 결과