[코드트리 조별과제] 흰검칠하기 C++ 풀이

---

알고리즘 분류

• 시뮬레이션
• 구현

---

문제 설명

일직선으로 무한히 나열된 타일이 있습니다. 아무 타일에서 시작하여 n번의 명령에 걸쳐 움직입니다. 명령은 "x L", "x R" 형태로만 주어지며, "x L"의 경우 왼쪽으로 이동하면서 현재 위치 타일포함 총 x칸의 타일을 흰색으로 연속하게 칠하고, "x R"의 경우 오른쪽으로 이동하면서 현재 위치 타일포함 총 x칸의 타일을 검은색으로 연속하게 칠함을 뜻합니다. 각 명령 이후에는 마지막으로 칠한 타일 위치에 서있는다고 가정합니다. 타일의 색은 덧칠해지면 마지막으로 칠해진 색으로 바뀌는데, 만약 타일 하나가 순서 상관없이 흰색과 검은색으로 각각 두 번 이상 칠해지면 회색으로 바뀌고 더 이상 바뀌지 않습니다. 모든 명령을 실행한 뒤의 흰색, 검은색, 회색의 타일 수를 각각 출력하는 프로그램을 작성해 보세요.

---

입력 설명

첫 번째 줄에는 n이 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 명령이 주어집니다. 형태는 “x L” 혹은 “x R”입니다.

• 1 ≤ n ≤ 1,000
• 1 ≤ x ≤ 100

---

출력 설명

첫 번째 줄에 모든 명령을 실행하고 난 뒤의 흰색, 검은색, 회색 타일 수를 각각 공백을 사이에 두고 출력합니다.

---

예제 입력

4
4 R
5 L
7 R
4 L

 

5
1 L
1 L
1 R
2 R
1 L

---

예제 출력

2 3 2

1 0 1

---

아이디어

색, 검은색으로 바뀐 횟수, 흰색으로 바뀐 횟수를 tuple형식으로 저장한다.

오른쪽으로 가면 색을 검은색으로 변경, 검은색으로 바뀐 횟수 1 증가해주고

왼쪽으로 가면 색을 흰색으로 변경, 흰색으로 바뀐 횟수 1 증가해준다.

이후 검은색 흰색으로 바뀐 횟수가 각각 2회 이상이면 회색으로 카운트하고 아니라면 숫자대로 카운트해서 출력한다.

---

알고리즘

아이디어와 알고리즘이 동일하다.

---

코드

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
int main() {
    int n, cur=150000;
    cin>>n;
    vector<tuple<char,int,int>> arr(300000,tuple<char,int,int>('N',0,0));
    for(int i=0;i<n;i++)
    {
        int a;
        char b;
        cin>>a>>b;
        if(b=='R')
        {
            for(int i=0;i<a;i++)
            {
                get<0>(arr[cur+i]) = 'B';
                get<1>(arr[cur+i])++;
            }
            cur += (a-1);
        }
        else
        {
            char fix = get<0>(arr[cur]);
            for(int i=0;i<a;i++)
            {
                    get<0>(arr[cur-i]) = 'W';
                    get<2>(arr[cur-i])++;
            }
            cur -= (a-1);
        }
    }
    int bl=0,wh=0,gr=0;
    for(auto &a : arr)
    {
        if(get<1>(a) >= 2 && get<2>(a) >= 2) gr++;
        else if(get<0>(a) == 'B' ) bl++;
        else if(get<0>(a) == 'W' ) wh++;
    }
    cout<<wh<<" "<<bl<<" "<<gr;
    return 0;
}

---

후기

문제 링크 -> https://www.codetree.ai/missions/5/problems/painting-white-black?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

오른쪽으로 가면 검은색으로 칠하고 왼쪽으로 가면 흰색으로 칠하는 것을 잘못 읽어서 한참을 헤맸다.

문제를 자세히 읽도록 하자.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!