danbibibi
article thumbnail
Published 2023. 3. 3. 21:33
BOJ 17615번: 볼 모으기 문제 풀이

문제

문제 바로가기> BOJ 17615번: 볼 모으기

 

17615번: 볼 모으기

첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주

www.acmicpc.net

 

풀이

크게는 총 2가지 경우가 있고, 그 안에서 또 2가지로 나뉘어 총 다음과 같은 4가지 경우가 있다.

 

1. 빨간 볼을 움직이는 경우

  • 왼쪽으로 움직이는 경우
  • 오른쪽으로 움직이는 경우

2. 파란 볼을 움직이는 경우

  • 왼쪽으로 움직이는 경우
  • 오른쪽으로 움직이는 경우

위 4가지 경우에서 최솟값을 찾아주면 되는 간단한 문제였다 ㅎㅎ

처음에 너무 복잡하게 생각하려고 하다보니 오히려 어렵게 느껴졌었다 ,,

 

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

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

    int N; cin >> N;
    string balls; cin >> balls;

    int ans = 500001, idx, move;

    // move blue →
    idx=N-1; move=0;
    while(balls[idx]=='B') idx--;
    for(int i=0; i<idx; i++){ if(balls[i]=='B') move++; }
    ans = min(ans, move);

    // move blue ←
    idx=0; move=0;
    while(balls[idx]=='B') idx++;
    for(int i=idx; i<N; i++){ if(balls[i]=='B') move++; }
    ans = min(ans, move);

    // move red →
    idx=N-1; move=0;
    while(balls[idx]=='R') idx--;
    for(int i=0; i<idx; i++){ if(balls[i]=='R') move++; }
    ans = min(ans, move);

    // move red ←
    idx=0; move=0;
    while(balls[idx]=='R') idx++;
    for(int i=idx; i<N; i++){ if(balls[i]=='R') move++; }
    ans = min(ans, move);

    cout << ans;
}
profile

danbibibi

@danbibibi

꿈을 꾸는 시간은 멈춰 있는 것이 아냐 두려워하지 마 멈추지 마 푸른 꿈속으로