[S1] 백준 17615번 볼 모으기 C++ 그리디 알고리즘

리뷰

 

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

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는문제... 근데... 문제가... 좀 이상하다.. 이게 맞는가 싶은데 맞네

 

 

전역 변수

• n : 공의 개수를 입력 받을 정수형 변수
• cnt : 각 케이스 마다 공을 이동할 횟수를 저장할 변수
• s : 공의 정보를 입력 받을 문자열 변수

 

함수

없음

 

 

문제풀이

1. n, s값을 입력 받고, 각 케이스마다 cnt 개수를 저장할 정수형 벡터 ans를 초기화 해준다.
2. 매 케이스마다 cnt를 0으로 초기화 해주고, B기준 양쪽, R기준 양쪽 총 4번의 케이스를 탐색해 준다.
3. R이 기준이라면 for문을 통해 최초로 B가 나올때를 찾고, 해당 인덱스부터 끝 인덱스까지 for문을 실행한다.
4. 이후 R이 등장한 순간마다 cnt를 증가시키고 탐색이 종료되면 break, ans벡터에 cnt를 추가해 준다.
5. B가 기준일때도 동일하게 진행해 준다, R, B모두 각각 s의 앞 뒤에서 탐색해 주어야 한다.
6. 4번의 케이스를 모두 실행하고 난 뒤 ans벡터에 저장된 값 중 가장 작은 값을 출력해 주면 된다.

 

참고 사항

아무 생각하지 말고 그냥 for문을 돌리면 통과하는 이상한 문제 너무 머리를 쓰지 말자

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, cnt;
string s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;

	vector<int> ans;
	cnt = 0;
	for (int i = n - 1; i > 0; i--) {
		if (s[i] == 'B') {
			for (int j = i - 1; j >= 0; j--) {
				if (s[j] == 'R') cnt++;
			}
			break;
		}
	}
	ans.push_back(cnt);

	cnt = 0;
	for (int i = n - 1; i > 0; i--) {
		if (s[i] == 'R') {
			for (int j = i - 1; j >= 0; j--) {
				if (s[j] == 'B')cnt++;
			}
			break;
		}
	}
	ans.push_back(cnt);

	cnt = 0;
	for (int i = 0; i < n - 1; i++) {
		if (s[i] == 'B') {
			for (int j = i + 1; j < n; j++) {
				if (s[j] == 'R') cnt++;
			}
			break;
		}
	}
	ans.push_back(cnt);

	cnt = 0;
	for (int i = 0; i < n - 1; i++) {
		if (s[i] == 'R') {
			for (int j = i + 1; j < n; j++) {
				if (s[j] == 'B') cnt++;
			}
			break;
		}
	}
	ans.push_back(cnt);


	cout << *min_element(ans.begin(), ans.end());
}