Codeforces Round #616 (Div. 2) - A. Even But Not Even

http://codeforces.com/contest/1291/problem/A

Problem - A - Codeforces

문제 이해

 주어진 문자열에 각 요소의 총합이 2로 나누어지고 원래 문자열의 2로 나누어지지 않는 수를 Even But Not Even이라고 한다. 즉 주어진 문자열(숫자)이 EBNE 가 인지 아닌지 판단한 하는 문제이다.

문자열에서 특정 요소를 제거하여 EBNE 인지 아닌지 판별하는 알고리즘을 구현 하면 된다.

 

제약 사항

입력으로 들어오는 N 의 값은 3000 이하이다.

전체의 합은 3000 이 넘지 않는다.

지울 수 있는 숫자 배열의 요소는 N-1이다. 

 

접근법

 이중 반복문을 통하여 N부터 N -1까지 계산한다고 가정하였을 때 N의 MAX는 3000 임으로 9000000(3000x3000)의 계산 과정이 필요하다. 문제에서 time limit per test는 1초임으로 bruth-force로 가능하다.

 

숫자	숫자는 2로 나누어 나머지가 있는가	총합은 2로 나누어져야함	판별
1227	O	총합은 12 나누어진다. O	O

 

두 가지 조건이 보인다.

 

숫자의 마지막은 홀수로 끝나야 2로 나눌 수 문제의 제약사항에 부합된다.

숫자의 모든 요소의 총합은 2로 나누어 떨어져야 한다.

 

lastValue = arr[n - i - 1]; // 마지막 요소

// sum 은 총합
if (sum % 2 == 0 && (lastValue & 1)) {
	// 출력후 종료
}

 

Source

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
//#include <map>
#include <set>
#include <stack>
#include <cstring>
 
using namespace std;
#define MAX_SIZE 100
#define INF 0x7fffffff
 
int main() {
 
    int t; cin >> t;
 
    while (t--) {
        
 
        int n; cin >> n;
 
        string str; cin >> str;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = str[i] - '0';
        }
        
        bool find = false;
        for (int i = 0; i < n; i++) {
 
            int lastValue = 0;
            int sum = 0;
            for (int j = 0; j < n-i; j++) {
                sum += arr[j];
            }
            lastValue = arr[n - i - 1];
            if (sum % 2 == 0 && (lastValue & 1)) {
                
                for (int x = 0; x < n - i; x++) {
                    cout << arr[x];
                }
                cout << "\n";
                find = true;
                break;
            }
        }
        if (find == false) {
            cout << -1 << "\n";
        }
    }
    return 0;
}