[BOJ] 볼 모으기 17615번 C++

2024. 9. 30. 17:32· Algorithm
목차
  1.  
  2. 접근 방식
  3. 코드

문제

빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.

  1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
  2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.

 

반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.

 

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.

입력

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

출력

최소 이동횟수를 출력한다.

서브태스크

번호배점제한
1 15 N ≤ 10
2 22 N ≤ 1,000
3 14 N ≤ 500,000, 처음 상태에서 모든 파란 공은 연속해서 존재한다.
4 49 원래의 제약조건 이외에 아무 제약조건이 없다.

 

접근 방식

 

생각보다 풀이를 떠올리기 쉽지 않았던 문제였다..

구현은 생각보다 간단하다

빨간볼, 파란볼에 대해 총 4가지 경우를 모두 계산해 최소값을 구하면된다.

1. 빨간볼을 왼쪽으로 모는 경우

2. 파란볼을 왼쪽으로 모는 경우

3. 빨간볼을 오른쪽으로 모는 경우

4. 파란볼을 오른쪽으로 모는 경우

 

이를 위해 각 경우에서의 이동 횟수를 계산하면 된다.

예를 들어, 빨간볼을 모두 왼쪽으로 모으려면, 왼쪽에서 연속된 빨간색 구간은 그래도 두고, 그 뒤에 나오는 모든 빨간색을 이동시켜야 한다.

따라서, 왼쪽에 연속된 빨간볼의 개수를 모두 구하고

전체 빨간볼의 개수에서 왼쪽에 연속된 빨간볼의 개수(이동하지 않아도 되는 빨간볼의 개수) 를 빼면된다.

 

즉, 모든 경우에 대해 위의 방식으로 이동 횟수를 구한 뒤, 가장 최소값을 구하면된다.

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;cin>>n;
    string str; cin>>str;

    int leftR = 0, leftB = 0, rightR = 0, rightB = 0;

    for(int i=0; i<n; i++) {
        if(str[i] == 'R') leftR++;
        else break;
    }

     for(int i=0; i<n; i++) {
        if(str[i] == 'B') leftB++;
        else break;
    }

    for(int i=n-1; i>=0; i--) {
        if(str[i] == 'R') rightR++;
        else break;
    }

    for(int i=n-1; i>=0; i--) {
        if(str[i] == 'B') rightB++;
        else break;
    }

    int totalR = count(str.begin(), str.end(), 'R');
    int totalB = count(str.begin(), str.end(), 'B');

    int result = min({totalR - leftR, totalB - leftB, totalR - rightR, totalB - rightB});

    cout<<result;



    
}

'Algorithm' 카테고리의 다른 글

[BOJ] 다리 놓기 1010번 C++  (1) 2024.10.01
[BOJ] 전구와 스위치 2138번 C++  (0) 2024.09.30
[BOJ] 신입 사원 1946번 C++  (2) 2024.09.25
[BOJ] 수 묶기 1744번 C++  (0) 2024.09.24
[BOJ] 나무 자르기 14247번 C++  (0) 2024.09.23
  1.  
  2. 접근 방식
  3. 코드
'Algorithm' 카테고리의 다른 글
  • [BOJ] 다리 놓기 1010번 C++
  • [BOJ] 전구와 스위치 2138번 C++
  • [BOJ] 신입 사원 1946번 C++
  • [BOJ] 수 묶기 1744번 C++
따봉치치
따봉치치
김치치의개발블로그따봉치치 님의 블로그입니다.
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 스택
  • 백준
  • javascript
  • TOPCIT
  • 백트래킹
  • 자료구조
  • 그리디
  • Greedy
  • 문자열
  • Stack
  • 우선순위 큐
  • dp
  • CS
  • Fe
  • BFS
  • 탐욕 알고리즘
  • C++
  • 누적합
  • 그래프 탐색
  • 리액트
  • 모던 리액트 딥다이브
  • 모던 자바스크립트 딥다이브
  • 데이터베이스
  • 알고리즘
  • BOJ
  • typescript
  • 자바스크립트
  • 투 포인터
  • react
  • 완전탐색

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 볼 모으기 17615번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.