[BOJ 15886] 내 선물을 받아줘 2

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

15886번: 내 선물을 받아줘 2

 

- 문제 요약

 

문자열의 길이 n, 길이 n인 문자열이 한 개 주어진다.

문자열은 E, W로 이루어져 있고, 이 문자열 위 어떤 부분에 선물을 놓았을 때 그걸 구사과가 가져가도록 해야 한다.

구사과는 문자열 위에서 움직일 수 있는데 E는 앞으로 한 칸, W는 뒤로 한 칸 가는 것을 의미한다.

시작 위치에 상관 없이 최소 몇 개의 칸 위에 선물을 놓아야 구사과가 선물을 가져갈 수 있는가?

 

 

- 알고리즘 정리

 

우선 Test case 1번을 가져와서 직접 시뮬레이션해보겠습니다.

 

6

EEWWEW

 

여기서 장기말을 움직이듯 인덱스를 빨간색으로 표시해가며 움직여보겠습니다.

 

우선 0번째 인덱스에서 시작하는 경우를 보겠습니다.

 

EEWWEW - (1)

EEWWEW - (2)

EEWWEW - (3)

 

0번째 인덱스부터 쭉 가다가 W를 만나니 (2)~(3)의 과정을 반복하는 걸 볼 수 있습니다.

그러면 1번째 인덱스와 2번째 인덱스 중 최소 한 곳에 선물을 놓으면 무조건 가져갈 수 있을 것입니다.

 

이제 4번째 인덱스에서 시작하는 경우를 보겠습니다.

 

EEWWEW - (1)

EEWWEW - (2)

 

이 역시 W를 만나니 (1)~(2)의 과정을 반복하고 있습니다.

아까와 같은 모양새이니 4번째 인덱스, 5번째 인덱스 둘 중 하나에 선물을 놓으면 무조건 가져갈 수 있을 것입니다.

 

이제 이쯤에서 우리는 "EW"라는 문자열이 몇 개가 포함되었는지가 중요하고,

"EW"문자열의 개수가 곧 답이라는 걸 알 수 있습니다.

 

이제 위 알고리즘을 따라 코드를 짜 보겠습니다.

 

 

- 코드 작성

 

별 다른 헤더 파일은 필요할 것 같지 않고, 그냥 반복문으로 풀면 될 것 같습니다.

 

#include<cstdio>
#include<iostream>
using namespace std;

int n,co;
string a;
char w;

int main(){
	cin>>n>>a;
	for(int i=0;i<a.size();i++){
		w=a[i];
		if(w=='W'&&a[i-1]=='E'){
			co++;
		}
	}
	cout<<co;
}

코드 제출 결과

요즘 dp문제에 찌들어 살아서인지 풀면서 자신감 충전을 좀 많이 했습니다.

알고리즘만 파악한다면 쉽게 풀리는 문제였습니다.