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

문제 설명

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

15886번: 내 선물을 받아줘 2

 

접근 방법 - 문자열에 대한 기본적인 그래프 탐색 문제

백준의 15886번 문제는 문자열에 대한 기본적인 그래프 탐색 연산을 수행해야 하는 문제이다.

해당 문제는, 구사과에게 선물을 전달하기 위해 필요한 선물의 최솟값을 구하여 출력해야 하는 문제이다.

이때 입력값으론 하나의 문자열이 나타나고 이에 따라 구사과의 움직임을 아래와 같다.

E: 이 문자를 만나면, 현재 위치(x)에서 오른쪽(x+1)으로 이동한다.
W: 이 문자를 만나면, 현재 위치(x)에서 왼쪽(x-1)으로 이동한다.

개인적으로, DFS 및 BFS 문제를 다루기 전에 풀어보기 좋은 문제일 것이라 생각한다.

필자는 문제를 자세히 보다 한 가지 규칙을 발견하였고, 이를 통해서 문제를 해결할 수 있었다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 문자열의 길이(n)와 문자열(map)을 순차적으로 입력받는다.

(이때, 정수와 문자열을 연이어 입력받기 때문에 반드시 그 중간에 버퍼를 비워주어야 한다.)

(필자의 경우엔 cpp를 사용하고 있기 때문에 cin.ignore()을 사용하였다.)

 

2) 최소로 필요한 선물의 개수를 카운팅 할 변수 cnt를 0으로 초기화하여 선언한다.

 

3) 반복문을 이용하여, map을 탐색하며 아래의 연산을 취한다.

- 만일, 현재 탐색값이 'W'이며 그 이전 값이 'E'인 경우엔 cnt에 1을 더하도록 한다.

'W'를 만나면 왼쪽으로 이동하고 'E'를 만나면 오른쪽으로 이동한다.
이를 염두하면 구사과가 머무를 수밖에 없는 구간이 생기는데, 이는 즉 EW로 이루어진 구간이다.
이 구간의 개수만 카운팅 하면 정답이 나온다.

 

4) 연산이 완료되었다면, 최종적으로 저장된 cnt의 값을 출력한 뒤 실행 종료한다.

 

추가 설명

다른 사람도 그랬을 듯 하지만, 필자는 3)에 나타난 규칙을 생각할 때 예외적인 상황도 고려했었다.

WE의 정답이 2일 것처럼, 양 옆의 2개 구간에 선물을 두어야 할 것 같은 예외를 생각하며 코드를 작성해보기도 했었다.

근데 결과부터 말하자면, 그 예외를 생각할 필요가 없는 조건이 문제에 미리 제시되어있었다.

문제를 자세히 보면, "지도에 쓰여있는 대로 이동했을 때, 지도를 벗어나는 경우는 없다."라는 설명이 있을 것이다.

이는 즉, 구사과는 입력된 문자열 안에서만 이동을 한다는 것을 뜻한다.

그렇기 때문에 모든 테스트 케이스의 시작 값은 E이며 마지막 값은 W라서 이러한 예외를 생각할 필요가 없는 것이다.

필자와 같은 생각을 했을 사람이 적지 않을 것 같아 이 설명을 추가로 작성해놓는다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 15886번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	cin.ignore();
	string map;
	cin >> map;

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (map[i] == 'W' && map[i - 1] == 'E') {
			cnt++;
		}
	}

	cout << cnt << endl;
}

 

제출 결과

(2022.10.27 백준 15886번 문제 제출 결과)