[C++] 백준 1639번:행운의 티켓(브루트포스 알고리즘)

문제링크

1639번: 행운의 티켓

문제

프로야구단 다숌 자이언츠에서는 야구장에 오는 손님에게 티켓을 나누어준다. 그리고 나서 그 티켓 중에 다음과 같은 규칙을 가진 티켓을 행운의 티켓이라고 하며, 그 티켓을 가진 사람들에게 상품을 나누어준다.

행운의 티켓은 정확하게 2*N자리로 이루어진 티켓이다. 왼쪽 N자리의 합과 오른쪽 N자리의 합이 일치하면 그 티켓은 행운의 티켓이라고 한다.

숌은 티켓 번호를 조작하려고 한다. 어떤 문자열이 주어지면, 그 문자열의 연속된 부분 문자열중 행운의 티켓 규칙을 만족하는 최대 부분 문자열의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. 문자열 S는 1보다 크거나 같고, 9보다 작거나 같은 수만 입력으로 들어오며, 문자열의 길이는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 주어진 입력의 연속된 부분 문자열 중 행운의 티켓 규칙을 만족하는 부분 문자열의 최대 길이를 출력하시오. 찾을 수 없다면 0을 출력한다.

 

풀이

문제를 잘못 이해하고 고민했다. 입력 하는 것은 그냥 문자열일 뿐이고 이 문자열 중에서 행운의 티켓 규칙을 만족하는 가장 긴 문자열의 길이를 출력하는 것이 문제다.

2*N의 길이를 정하여 문자열 전체를 탐색하고 좌측 N개의 문자의 합과 우측 N개의 문자의 합이 같은지 판단해야 한다.

만약 짧은 문자열부터 확인한다면 문자열이 가장 길 때까지 반복하여 확인을 해야 하기 때문에 긴 문자열부터 탐색하였다.

문자열의 길이를 시작 지점, 끝 지점이라는 변수를 선언하고 값을 주어 설정해주었다.

해당 문자열의 좌측 합 우측 합을 확인하여 같다면 출력하고 종료한다.

코드

#include <iostream>
#include <vector>
using namespace std;
 
int arr[101], Start, End;
string n;
bool possible;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    int size = n.size();
    
    for (int i = 0; i < n.size(); i++) {
        arr[i] = n[i] - '0';
    }
 
    Start = 0;
    // 홀수면 짝수로 바꿔주는 과정
    // while에서 -2를 해주기 때문에 +2를 추가해줌
    if (size % 2 == 0) {
        End = size + 2;
    }
    else {
        End = size - 1 + 2;
    }
 
    // 2보다 커야만 옆으로 양쪽으로 확인 가능
    while (End > 2) {
        Start = 0;
        End = End - 2;  // 끝 칸을 두 자리 없애서 -2
        int s = Start;
        int e = End;
 
        while (e <= size) {
            int mid = (s + e) / 2;
            // 좌측 값의 합을 저장할 변수
            int left = 0;
            // 우측 값의 합을 저장할 변수
            int right = 0;
 
            // 좌측 값의 합
            for (int i = s; i < mid; i++) {
                left = left + arr[i];
            }
 
            // 우측 값의 합
            for (int i = mid; i < e; i++) {
                right = right + arr[i];
            }
 
            // 같다면 출력 후 종료
            if (left == right) {
                cout << End;
                return 0;
            }
            s++;
            e++;
        }
    }
    cout << 0;
}

 

메모

[C++] 백준 1120번:문자열(브루트포스 알고리즘)