BOJ 2684번: 동전 게임

문제

동전게임은 주로 두 사람이 함께 즐기는 게임이다. 이 중 3-동전게임은 여러 명이 할 수 있는 게임이다. 각 사람은 각각 3-동전수열 중 하나를 선택한다. 3-동전수열이란 앞 뒤 앞과 같은 수열이고, 8가지(뒤뒤뒤,뒤뒤앞,뒤앞뒤,뒤앞앞,앞뒤뒤,앞뒤앞,앞앞뒤,앞앞앞)가 있다.

이제 심판은 동전 1개를 40번 던진다. 그 다음 심판은 동전이 앞인지 뒤인지를 던진 순서대로 종이에 적는다. 그 다음 3-동전수열이 각각 몇 번씩 나왔는지 기록한다. 가장 많이 나온 수열을 선택한 사람이 이긴다.

동전 40번 던진 결과가 주어졌을 때, 3-동전수열이 각각 몇 번 나왔는지를 출력하는 프로그램을 작성하시오. 예를 들어, 40개의 동전이 모두 앞면일 경우 앞앞앞은 38번 나타난다.

입력

첫째 줄에 테스트 케이스의 개수 P(1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 동전을 40번 던진 결과가 주어진다. 이때, 앞면은 H로, 뒷면은 T로 표현한다.

출력

각 테스트 케이스마다 3-동전수열이 몇 번 나타났는지를 출력한다. 뒤뒤뒤, 뒤뒤앞, 뒤앞뒤, 뒤앞앞, 앞뒤뒤, 앞뒤앞, 앞앞뒤, 앞앞앞 순서대로 공백으로 구분해서 출력한다.

---

문제 풀이 - 성공

TTT TTH THT THH HTT HTH HHT HHH

• 8가지 수열의 개수를 저장할 배열을 만들고 모든 경우를 조건문으로 정의해서 원소를 하나 씩 검사했다.
• i번째 원소와 i+1번째, i+2번째 원소가 어떤 경우의 수를 만드는 지 검사해서 해당 수열 개수를 1 증가 시킨다.

시간 복잡도: T(p) = p *(8 + (38 * 4) + 8) => O(n)

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

int arr[8]; // 각 수열의 개수가 저장될 배열

int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int p, i, j;
    string coin;
    cin >> p;

    for(i = 0; i < p; i++) {
        for (j = 0; j < 8; j++) { arr[j] = 0; }
        cin >> coin;

        for (j = 0; j < 38; j++) {
            if (coin[j] == 'T') {
                if (coin[j + 1] == 'T') {
                    if (coin[j + 2] == 'T') { arr[0]++; }
                    else { arr[1]++; }
                }
                else {
                    if(coin[j + 2] == 'T') { arr[2]++; }
                    else { arr[3]++; }
                }
            }
            else { // coin[j] = 'H'
                if (coin[j + 1] == 'T') {
                    if (coin[j + 2] == 'T') { arr[4]++; }
                    else { arr[5]++; }
                }
                else {
                    if (coin[j + 2] == 'T') { arr[6]++; }
                    else { arr[7]++; }
                }
            }
        }

        for (j = 0; j < 8; j++) { cout << arr[j] << " "; }
        cout << '\n';
    }

    return 0;
}