문제 이해 단계
https://www.acmicpc.net/problem/20365
문제 자체는 이해하기 쉽다.
이웃한 번호까지 한 번에 같은 색으로 칠한다.
예를 들어 1번 7번을 선택하면, 1~7번까지 모두 같은 색으로 칠해진다는 뜻이다.
이런 식으로 했을 때,
모든 번호를 원하는 색으로 칠하는 최소 횟수를 구하라는 것이 문제이다.
문제 접근 단계
어떻게 하면 최소로 할 수 있을까?
라고 생각을 하다가 예시에 나와있는 BBRBRBBR로 생각을 했다.
첫 번째로 B로 최대한 많은 색을 칠한다.(1~7번)
이후 사이사이 박혀있는 R을 칠하는데
이웃한 것이 있다면 같은 횟수로 간주한다.
하지만 여기서는 R이 다들 떨어져 있기 때문에, 하나씩 간주했다.
그래서 (1~7번), (3번), (5번), (8번)
총 4번이 최소 횟수였다.
이런 기전으로 흘러갔을 때, 여러 B들 사이에 R이 박혀있다고 생각하니까
R을 기준으로 문자를 나누는 방식이 떠올랐다.
예를 들어, BBRBRBBR은 R을 구분자로 생각하면
BB/B/BB가 되는 것이다.
총 3개의 그룹이 나오는데, 마지막에 R은 칠해줘야 하기 때문에
+1을 한 4가 답이 된다.
이런 방식으로 풀면 될 것 같다고
구분자를 이용한 분리라는 측면으로 생각했다.
만약 BBRRBB라면 BB/BB로 분리된다.
그리고 시작과 끝이 R로 끝나지 않기 때문에
따로 R로 칠해줄 필요가 없어 답은 2가 된다.
즉 해당 알고리즘은 두 가지로 분리해서 생각할 수 있다.
Point.1
문자 시작이나 끝이 R인 경우
RBBBBR인 경우를 생각해 보자.
1~6번째를 R로 만들고
2~5번째를 B로 만들면 최소 2회가 답이다.
R을 분리자로 하면 /BBBB/가 된다.
RBBBB인 경우를 생각해 보자.
1번째에 R,2~5번째의 B를 하면 최소 2회가 답이다.
R을 분리자로 하면 /BBBB가 된다.
즉, 위에서 알 수 있는 것은,
문자 시작이나 끝에 R이 들어갈 경우, 분리된 그룹+1 한 것이 답이 된다는 것이다.
Point.2
문자 시작이나 끝이 R이 아닌 경우
BBRRBB인 경우를 생각해 보자.
최소 횟수는 2이다.
분리해 보면 BB//BB이기 때문에 그룹은 2개다.
시작과 끝에 이미 B를 칠해줬기 때문에
R을 더 이상 덧칠할 필요가 없다.
즉, 문자 시작과 끝이 B라면 나눠진 그룹의 개수가 답이 된다.
Point.3
R이 B보다 훨씬 많으면 R을 분리자로 하는 것이 부적절하지 않나?
예를 들어, RRRBRRR이 있다고 생각해 보면
B를 구분자로 하는 것이 더 적절해 보인다.
하지만 R을 구분자로 한 루틴이 정상작동한다면 딱히 문제 될 것이 없다.
R을 구분자로 분리하면 ///B///가 된다.
시작 또는 끝이 R이기 때문에 최소 횟수는 총 2개 된다.
실제로 해당 입력의 최솟값도 2이다.
즉, 이렇게 해도 아무런 문제가 없음을 알 수 있다.
문제 구현 단계
string value;
cin >> value;
value.push_back('R');
stringstream ss(value);
vector<string> word;
int answer = 0;
while (getline(ss, value, 'R')) {
if (value.empty()) word.push_back("0");
else
{
word.push_back(value);
answer++;
}
}
if (word[0] == "0" || word[word.size() - 1] == "0") answer++;R을 분리자로 사용하기 위해 sstream이라는 라이브러리를 사용하였다.
'R'을 구분자로 하여 ss안에 있는 문자열을 그룹으로 하여 value에 저장하였다.
그 후, word 벡터 안에 그룹별로 저장하는 작업을 하였다.
여기서 눈여겨봐야 될 점은 값이 비어있을 경우(value.empty()) 0을 저장해 준다는 점이다.
만약 BBRRBB의 경우, BB/0/BB 이런 식으로 저장해 주기 위함이다.
이런 식으로 저장하는 이유는
문자열이 R로 시작하거나 끝나는 것을 "0"문자열로 알리기 위함이다.
그렇기 때문에 맨 처음 입력값을 받은 뒤에 뒤에 R을 붙여 준 것이다.
이는 RBBR를 입력받았다면, sstream에 의해서 0/BB로만 처리된다.
한마디로 문자열 끝에 R이 붙는지를 알 수가 없다.
그래서 끝에 R을 하나 더 붙여줌으로써,
0/BB/0으로 저장되게 하여 끝에 R이 붙는지를 확인하는 것이다.
그리고 만약 값이 존재한다면, 하나의 그룹으로 간주하여 answer++를 해준다.
반복이 끝난 뒤에 word에 첫 번째 그룹(문자열 첫 번째 글자),
word의 마지막 그룹(마지막 글자)이
0인지 아닌지 체크하여 맞으면 answer++를 해준다.
마지막으로는 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int n;
cin >> n;
string value;
cin >> value;
value.push_back('R');
stringstream ss(value);
vector<string> word;
int answer = 0;
while (getline(ss, value, 'R')) {
if (value.empty()) word.push_back("0");
else
{
word.push_back(value);
answer++;
}
}
if (word[0] == "0" || word[word.size() - 1] == "0") answer++;
cout << answer;
}
시행착오
크게 시행착오는 없었지만 sstream을 사용하여 분리할 때
마지막에 0이 들어가나 안 들어가나 체크하는 작업이 어려웠다.
결국에는 꼼수일지는 몰라도 R을 하나 더 붙임으로써 0이 구현되도록 하였다.