[백준] 15886번 : 내 선물을 받아줘 2 (C++)

15886번 : 내 선물을 받아줘 2

---

문제)

욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.

구사과가 있는 곳은 1×N 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (1, x)로 나타낼 수 있으며, (1, x)는 왼쪽에서부터 x번째 칸을 의미한다.

지도의 각 칸에는 E, W중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한다. 구사과의 위치가 (1, x)인 경우에 E가 쓰여져 있는 칸에 서 있었다면, (1, x+1)로, W의 경우에는 (1, x-1)로 순간이동한다. 구사과는 지치지 않기 때문에, 계속해서 이동한다.

욱제는 구사과의 위치를 모르기 때문에, 구사과가 이동을 시작하는 위치와 관계없이 선물을 주는 방법을 알아내려고 한다. 최소 몇 개의 칸 위에 선물을 놓으면, 구사과가 항상 선물을 가져가는지 구하는 프로그램을 작성하시오. 선물이 놓여진 칸에 구사과가 이동하면, 구사과는 항상 선물을 가져간다.

 

 

 

입력 :

첫째 줄에 골목길의 길이 N이 주어진다. (2 ≤ N ≤ 1,000)

둘째 줄에 길이 N짜리 구사과가 있는 곳의 지도가 주어진다.

지도에 쓰여 있는대로 이동했을 때, 지도를 벗어나는 경우는 없다.

 

 

 

출력 :

첫째 줄에 최소 몇 개의 칸에 선물을 놓아야 하는지 출력한다.

 

 

 

 

 

 

풀이)

 

처음에는 DFS나 BFS를 이용하여 플러드 필을 하듯이 하려고 했으나,

 

이 경우에는 EEWW의 경우에 2개가 나오게 된다. 따라서 이 방법은 사용하지 못했고,

 

가만히 예제의 패턴을 살펴보니, 한 방법을 제외하고 같은 방식을 사용할 수 있었다.

 

맨 처음 W가 나오는 패턴을 제외하고는 E의 뭉치?가 나오는 갯수가 답이 된다.

 

따라서 W가 처음 나왔을 때만 cnt를 1부터 시작하고, 이외에는 E 그룹의 개수만 세어주면 된다.

 

// 15886. 내 선물을 받아줘 2
#include <iostream>
#include <string>
 
using namespace std;
 
int n;
string s;
 
int main()
{
    cin >> n >> s;
 
    int cnt = 0;
    bool flag = 0;
 
    if (s[0] == 'W') cnt++;
 
    for (int i = 0; i < n; i++)
    {
        if (!flag && s[i] == 'E')
        {
            flag = 1;
            cnt++;
        }
        else if (s[i] == 'W')
        {
            flag = 0;
        }
    }
 
    cout << cnt;
 
    return 0;
}
 

---

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

15886번: 내 선물을 받아줘 2