[class 1]백준 OX퀴즈(8958번) 풀이 (C++/Python)

문제 : OX퀴즈(8958번)(Bronze II)

문제 링크 : https://www.acmicpc.net/problem/8958
출처 : Baekjoon Online Judge

 

 

O이면 1점 획득인데 O가 2연속이면 1+2 = 3점을 획득합니다.

그리고 O가 3연속이면 1+2+3 = 6점 획득하는 방식입니다.

하지만 단 한 번이라도 X로 만나서 연속이 깨지면 그 즉시 0점 획득이고 그 다음에 다시 O가 오면 1점 획득하는 방식입니다.

OOXXOXXOOO

예시 입력이 다음과 같습니다.

우선 index 0부터 시작합니다.

 

(0번째 원소)

초기 count는 0입니다.

O이니 count는 1이 되고 점수(result)를 count만큼 더해서 1점이 됩니다.

(1번째 원소)

O이므로 count++ 되고 count는 2가 됩니다.

이 때 O이니 result += count를 통해 총 3점이 됩니다.

(2번째 원소)

X이므로 count = 0이 되고 별도의 연산을 하지 않습니다.

(3번째 원소)

X이므로 count = 0이 되고 별도의 연산을 하지 않습니다.

...

이렇게 해서 1 + 2 + 0 + 0 + 1 + 0 + 0 + 1 + 2 + 3 = 10점이 됩니다.

 

이것을 통해 O인 경우와 X인 경우는 다음과 같은 작업을 진행합니다.

[O인 경우]

count++;

result += count;

[X인 경우]

count = 0;

 

이제 이것을 C++로 구현하겠습니다.

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

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

    int t;
    cin >> t;

    while(t--) {
        string ox;
        cin >> ox;

        int count = 0;
        int size = ox.size();

        int result = 0;

        for(int i = 0; i < size; i++) {
            if(ox[i] == 'O') {
                count++;
                result += count;
            } else count = 0;
        }

        cout << result << '\n';
    }

    return 0;
}

 

같은 논리를 Python으로도 구현할 수 있습니다.

import sys

input = sys.stdin.readline

T:int = int(input().rstrip())

for i in range(T) :
    OX:str = input().rstrip()
    
    count:int = 0
    result:int = 0
    
    for j in range(len(OX)) :
        if OX[j] == "O" :
            count += 1
            result += count
        elif OX[j] == "X" :
            count = 0
            
    print(result)

 

추가로 Python은 split() 하나로 문자열을 리스트로 만들 수 있습니다.

예시로 OOXXOXXOOO일 때 "X" 기준으로 파싱한다면 ['OO', '', 'O', '', 'OOO']가 됩니다.

이 때 1부터 N까지의 합(시그마 공식)을 활용하면 수학적으로 해결할 수 있습니다.

import sys

input = sys.stdin.readline

def sigma(N:int) -> int :
    return N * (N + 1) // 2

T:int = int(input().rstrip())
for _ in range(T) :
    OX:str = input().rstrip()
    
    L:list = list(map(str, OX.split("X")))
    
    result:int = 0
    
    for item in L :
        result += sigma(len(item))
        
    print(result)

이렇게 해도 계산을 빠르게 할 수 있습니다.