😊 이번 주 실력진단 결과!!

지난 주 487점 보다는 올랐다!!
이번 연휴에 열심히 공부해서 얼른얼른 진도를 나가야 겠다는 생각을 했다.. 🤣
공부하시는 모든 분들 화이팅입니다!!! 좋은 결과 있을 거예요!!!

☝️ 신기한 타일 뒤집기 문제

코드 트리 문제 링크

문제

일직선으로 무한히 나열된 회색 타일이 있습니다. 이 타일은 신기한 타일이기 때문에, 현재 타일의 색이 어떤 색인지와는 상관없이 왼쪽으로 뒤집으면 흰색으로 바뀌고, 오른쪽으로 뒤집으면 검은색으로 바뀌게 됩니다.
아무 타일에서 시작하여 n번의 명령에 걸쳐 움직입니다. 명령은 "x L", "x R" 형태로만 주어지며, "x L"의 경우 왼쪽으로 이동하며 순서대로 현재 위치 타일포함 총 x칸의 타일을 왼쪽으로 뒤집습니다. "x R"의 경우 오른쪽으로 이동하며 순서대로 현재 위치 타일포함 총 x칸의 타일을 오른쪽으로 뒤집습니다. 각 명령 이후에는 마지막으로 뒤집은 타일 위치에 서있는다고 가정합니다.

모든 명령을 실행한 뒤의 흰색, 검은색 타일 수를 각각 출력하는 프로그램을 작성해보세요.

입력 형식

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

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

1 ≤ n ≤ 1000
1 ≤ x ≤ 100

출력 형식

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

입출력 예제

예제1 입력:
4
4 R
5 L
7 R
4 L

출력:
4 3

예제2 입력:
2
10 R
11 L

출력:
11 0

✌️ 구간 칠하기!

코드 트리에서 구간 칠하기 문제를 쭉 풀어봤다면 결국 구간 칠하기는 1차원 배열로 구간을 표현한다는 것이 관건이다!

예를 들어 구간 [2, 5], [4, 5], [1, 2]이 주어지고 각 구간을 칠한다고 해보자.
그러면 각 구간을 [x1, x2]로 생각하고 x1 배열과 x2 배열을 만든다.

[2, 5]를 입력받으면 배열에 다음과 같이 저장한다.다음으로 [4, 5]가 주어지면 다음과 같이 된다. 마지막으로 [1, 2]가 주어지면 다음과 같다.

이제 구간을 칠 할 checked라는 1차원 배열을 만든다. 그 다음 x1[0], x2[0] ~ x1[2], x2[2]까지의 값에 해당하는 checked의 인덱스를 찾아 해당 인덱스의 값을 1씩 증가시킨다. 코드로 표현하면 다음과 같다!!

 for(int i = 0; i < 3; i++)
     for(int j = x1[i]; j <= x2[i]; j++)
            checked[j]++;

만약 문제에서 주어지는 좌표의 범위가 음수가 있다면 적당한 OFFSET을 찾아서 모두 양수화를 해줘야 한다.
예를 들어 [-2, 5] 구간을 칠한다면 checked 배열에는 음수 인덱스가 없으니 좌표를 모두 양수화를 시켜준다. x 값이 -100에서 100 사이의 값으로 주어진다면 OFFSET을 최소 100으로 잡아준 뒤 좌표를 OFFSET만큼 증가시켜준다. 그러면 [-2, 5]는 OFFSET만큼 증가시키면 [98, 105]이 될테고 checked에서 해당 좌표 구간을 칠해주면 된다.

또한 구간을 칠하는 것이 왼쪽, 오른쪽으로 이동하는 문제라면 현재 위치에서 왼쪽, 오른쪽 이동하는 부분도 고려해야한다!
현재 위치를 담을 변수를 선언하고 적절한 위치에서 시작해서 왼쪽으로 이동하면 현재위치를 감소시키고 오른쪽으로 이동하면 현재위치를 증가시키면서 이동해야 한다.

🤟 문제 풀어보기!

이 문제에서 중요한 점은 배열의 크기를 설정하는 것이다. 문제에서 무한히 이어진 타일이 주어지고 왼쪽, 오른쪽으로 어떻게 얼만큼 이동할지 모르기 때문에 배열의 크기를 잘 지정해야 한다. 이 때, 이동하면서 음수 인덱스가 나오지 않도록 하기 위해서 최대 범위의 배열을 선언하고 그 중간 지점을 시작 위치로 잡아야 한다.
주어진 x의 범위는 1~100이고 n의 범위는 1~1000이다. 즉 x 좌표는 1~100사이의 값이 주어지고, 명령의 횟수는 최대 1000번이다. 그러면 어느 한쪽으로 최대로 움직인 x좌표는 100 x 1000 이니 100000이 된다. 그래서 MAX_X는 100000으로 설정했다. 또한 x가 왼쪽으로 최대한 갈 수도 있고 오른쪽으로 최대한 갈 수도 있으니 배열의 크기는 2 x 100000 + 1로 잡았다. +1은 해당 인덱스까지도 배열의 크기로 쓰기 위해서 +1 해주었다.

#include <iostream>

#define MAX_X 100000 //x의 최댓값 설정

int arr_x[2*MAX_X+1]; //배열의 최댓값 설정
int w, b;

using namespace std;

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

    int cur = MAX_X; //타일의 현재 위치는 배열의 중간으로 잡는다.

    for(int i=0; i<n; i++){
        int x;
        char c;
        cin >> x >> c;

        if(c == 'L'){ //왼쪽으로 가면서 흰색으로 뒤집기 (흰색은 1로 표현)
            while(x--) {
                arr_x[cur] = 1;
                if(x) cur--;
            }
        }else{ //오른쪽으로 가면서 검은색으로 뒤집기 (검은색은 2로 표현)
            while(x--) {
                arr_x[cur] = 2;
                if(x) cur++;
            }
        }
    }

    for(int i=0; i<=2*MAX_X+1; i++){ //흰색(1), 검은색(2) 타일의 개수 세기
        if(arr_x[i] == 1) w++; 
        else if(arr_x[i] == 2) b++;
    }

    cout << w << " " << b;
    return 0;
}