A. Donut Shops

    도넛을 낱개로 파는 첫번째 가게, 도넛을 묶음으로 파는 두번째 가게가 있다.

    첫번째 가게의 도넛의 가격 a, 묶음으로 파는 두번째 가게의 도넛의 가격 b개당 c 가 주어질 때

    도넛을 최소 x개 사야할 때 첫번째 가게가 이득일 수 있는 x, 두번째 가게가 이득일 수 있는 x를 찾아 출력하는 문제였다.

     

    간단하지만 시간이 좀 걸렸던 발상 + 수학문제이다.

    우선 첫번째 가게가 이득일 수 있는 최고의 경우는 1개만 사도될 때 일 것이다.

    따라서 a < c 이면 x = 1이 될 수 있다. 아닐 경우 이득일 경우가 존재하지 않을 것이다.

     

    두번째 가게가 이득일 수 있는 최고의 경우는 묶음 갯수만큼만 구매해야 할 때 이다.

    따라서 a * b > c  라면 b개를 샀을 때 두번째 가게가 이득이 될 수 있다.

     

    아래는 소스코드이다.

    더보기
    #include <bits/stdc++.h>
    #define endl '\n'
    #define pb push_back
    #define mp make_pair
    #define MOD 1000000007
    #define cont continue
    #define rep(i, n) for(int i = 0 ; i < (n) ; i++)
    #define all(x) (x).begin(), (x).end()
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    const ll INF = 987654321;
     
    int T;
     
    int main() {
      cin.tie(NULL);
      ios_base::sync_with_stdio(false); 
     
      cin >> T;
     
      while(T--) {
        ll a, b, c;
        cin >> a >> b >> c;
        ll ans1 = -1;
        ll ans2 = -1;
        if(a < c) {
          ans1 = 1;
        }
        if(c < a * b) {
          ans2 = b;
        }
        cout << ans1 << ' ' << ans2 << endl;
      }
    } 

     

    B. 01 Game

    게임 이론이다.

    1과 0으로 이루어진 문자열에서 인접한 문자가 다를 경우 그 둘을 삭제할 수 있다.

    삭제가 불가능할 경우 그사람의 패배. 선공은 앨리스이다.

    0과 1이 존재하는 문자열에서 0과 1 둘 중 적은 것은 항상 다른 수와 인접하게 될 것이다.

    따라서 지울 수 있는 횟수는 0과 1의 갯수중 최소 횟수가 될 것이다.

    선공은 앨리스이므로 횟수가 홀수일 경우 앨리스의 승리, 짝수일 경우 밥의 승리가 되겠다.

    아래는 소스코드이다.

    더보기
    #include <bits/stdc++.h>
    #define endl '\n'
    #define pb push_back
    #define mp make_pair
    #define MOD 1000000007
    #define cont continue
    #define rep(i, n) for(int i = 0 ; i < (n) ; i++)
    #define all(x) (x).begin(), (x).end()
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    const ll INF = 987654321;
     
    int T;
     
    int main() {
      cin.tie(NULL);
      ios_base::sync_with_stdio(false); 
     
      cin >> T;
     
      while(T--) {
        string s;
        cin >> s;
        bool flag = true;
        int one = 0;
        int zero = 0;
        for(int i = 0 ; i < s.size() ; i++) {
          if(s[i] == '0') zero++;
          if(s[i] == '1') one++;
        }
        int tmp = min(one, zero);
     
        if(tmp % 2 == 0) {
          cout << "NET" << endl;
        }
        else {
          cout << "DA" << endl;
        }
      }
    } 

     

    C. Pluses and Minuses

    +와 -로 이루어진 문자열이 이루어진다.

    다음 수도코드를 실행시켰을 때 나올 수 있는 res값을 출력하는 문제.

     

    코드를 보면 관찰할 수 있는 점은

    1. 0부터 inf로 증가하는 cur이 문자열을 모두 순회하는 동안 양수로 유지될 경우 프로그램이 종료된다.

    2. 문자열을 순회하던 도중 cur이 음수가 될 경우 문자열의 순회를 종료한다.

     

    cur은 0부터 증가하므로 cur이 0일때는 -1이 처음 등장하는 위치, cur이 1일때는 -2이 처음 등장하는 위치, ...를 찾고

    못찾았을 경우에는 문자열을 모두 순회한 뒤 양수로 종료되었다는 의미이므로 문자열 길이 만큼을 더해준 뒤 답을 출력했다.

     

    음수가 처음 등장하는 위치는 stl map을 이용했다.

     

    아래는 소스코드이다.

    더보기
    #include <bits/stdc++.h>
    #define endl '\n'
    #define pb push_back
    #define mp make_pair
    #define MOD 1000000007
    #define cont continue
    #define rep(i, n) for(int i = 0 ; i < (n) ; i++)
    #define all(x) (x).begin(), (x).end()
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    const ll INF = 987654321;
    
    int T;
    
    int main() {
      cin.tie(NULL);
      ios_base::sync_with_stdio(false); 
    
      cin >> T;
    
      while(T--) {
        string s;
        cin >> s;
        int num = 0;
        map<int, int> m;
        int minnum = INF;
        for(int i = 0 ; i < s.size() ; i++) {
          if(s[i] == '+') num++;
          else if(s[i] == '-') num--;
          if(num < 0) {
            if(m.find(num) == m.end()) {
              m.insert(mp(num, i + 1));
            }
          }
    
        }
        ll ans = 0;
        int cur = -1;
        while(1) {
          if(m.find(cur) == m.end()) {
            ans += s.size();
            break;
          }
          else {
            ans += m[cur];
          }
          cur--;
        }
        cout << ans << endl;
      }
    } 
    

    D. Maximum Sum on Even Positions

    배열의 구간 [L, R]의 서브스트링을 최대 한번 뒤집어서 짝수 인덱스의 합을 최대로 하여 그 합을 출력하는 문제

    대회 중에 풀긴 했지만 너무 늦게 풀었다.

    홀수개는 바꿔봐야 짝수 인덱스는 변하지 않는다는 걸 너무 늦게 발견했다.

     

    배열 7,3,1 을 생각해보자 이것을 3개를 전부 뒤집으면 1,3,7이되므로 짝수 인덱스는 1, 7과 7, 1로 동일하다.

    꼭 3개가 아니여도 홀수개를 뒤집었을 경우에는 짝수 인덱스는 동일하게 유지된다는 것을 알 수 있다.

    따라서 시작점이 0, 1일때로 나누어 수를 바꾸었을 때의 손익값을 저장하여 dp를 이용해 최대 연속구간합을 구해 둘 중 최댓값을 원래 짝수 인덱스의 합 값에서 더해주자.

    아래는 소스코드이다.

    더보기
    #include <bits/stdc++.h>
    #define endl '\n'
    #define pb push_back
    #define mp make_pair
    #define MOD 1000000007
    #define cont continue
    #define rep(i, n) for(int i = 0 ; i < (n) ; i++)
    #define all(x) (x).begin(), (x).end()
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    const ll INF = 987654321;
    
    int T;
    
    int main() {
      cin.tie(NULL);
      ios_base::sync_with_stdio(false); 
    
      cin >> T;
    
      while(T--) {
        int n;
        vector<ll> arr;
    
        cin >> n;
        ll sum = 0;
        for(int i = 0 ; i < n ; i++) {
          ll x;
          cin >> x;
          if(i % 2 == 0) sum += x;
          arr.pb(x);
        }
        if(n == 1) {
          cout << arr[0] << endl;
          continue;
        }
        else if(n == 2) {
          cout << max(arr[0], arr[1]) << endl;
          continue;
        }
        vector<ll> diff1;
        vector<ll> diff2;
    
        for(int i = 1 ; i < arr.size() ; i+= 2) {
          diff1.pb(arr[i] - arr[i - 1]);
        } 
    
        for(int i = 2 ; i < arr.size() ; i += 2) {
          diff2.pb(arr[i - 1] - arr[i]);
        }
    
        ll ans = 0;
        ll mx1 = 0;
        ll dp1[n + 1] = {};
        dp1[0] = max((ll)0, diff1[0]);
        mx1 = max(dp1[0], (ll)0);
        for(int i = 1 ; i < diff1.size() ; i++) {
          dp1[i] = max((ll)0, dp1[i - 1]) + diff1[i];
          mx1 = max(mx1, dp1[i]);
        }
        ans = max(ans, sum + mx1);
        ll mx2 = 0;
        ll dp2[n + 1] = {};
        dp2[0] = max((ll)0, diff2[0]);
        mx2 = max(dp2[0], (ll)0);
        for(int i = 1 ; i < diff2.size() ; i++) {
          dp2[i] = max((ll)0, dp2[i - 1]) + diff2[i];
          mx2 = max(mx2, dp2[i]);
        }
        ans = max(ans, sum + mx2);
        cout << ans << endl;
      }
    } 
    

     

     

    'Codeforces > Div. 2' 카테고리의 다른 글

    Codeforces Round #648 (Div. 2) A ~ D 풀이  (1) 2020.06.08
    Posted by 엄태호