c언어 17615번 볼 모으기 (백준)

#include <stdio.h>

int main(void) {
	int n,f=0,a=0,c=0;
	scanf("%d",&n);
	char s[n+1];
	scanf("%s",s);
	
	for(int i=0;i<n;i++) {
		if(s[i]=='B') f=1;
		if(f==1 && s[i]=='R') ++a;
	} 
	c=a;f=0;a=0;
	for(int i=0;i<n;i++) {
		if(s[i]=='R') f=1;
		if(f==1 && s[i]=='B') ++a;
	} 
	if(a && a<c)c=a; f=0;a=0;
	for(int i=n-1;i>=0;i--) {
		if(s[i]=='B') f=1;
		if(f==1 && s[i]=='R') ++a;
	}
	if(a && a<c)c=a;f=0;a=0;
	for(int i=n-1;i>=0;i--) {
		if(s[i]=='R') f=1;
		if(f==1 && s[i]=='B') ++a;
	}
	if(a && a<c)c=a;
	printf("%d",c);
}

 

풀이 : 그리디?

 

1. 왼쪽에서 출발, 오른쪽에서 출발 2가지 경우

2. 여기서 B 가 발견 된 다음 이후 나머지 A를 옮기는 경우, A가 발견된 다음 나머지 B를 옮기는 경우 

 

총 4가지 경우를 고려하면 됩니다.

 

그 중 가장 최솟값을 출력하면 됩니다.

 

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