[백준 / BOJ] C++ 27970 OX

27970번: OX

 

문제

https://www.acmicpc.net/problem/27970

27970번: OX

 

 

풀이

i번째 인덱스에 O가 있으면 이 O를 X로 바꾸기 위해서는 2^i번 연산을 수행해야 한다. O가 있는 인덱스 i에 대해 2^i의 합을 출력하면 된다. int 범위를 벗어날 수 있으므로 long long을 쓰고 모듈러 연산을 계속 해줘야 한다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long ans = 0, mul = 1, mod = 1e9 + 7;
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'O')
      ans += mul;
    ans %= mod;
    mul *= 2;
    mul %= mod;
  }
  cout << ans;
  return 0;
}

 

(아래는 비효율적인 매번 pow하는 풀이)

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

long long power(long long x, long long y) {
  if (y == 0)
    return 1;
  long long result = power(x, y / 2);
  if (y % 2 == 0)
    return result % 1000000007 * result % 1000000007;
  else
    return x * result % 1000000007 * result % 1000000007;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long ans = 0;
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++)
    if (s[i] == 'O')
      ans = ((ans % 1000000007) + (power(2, i) % 1000000007)) % 1000000007;
  cout << ans;
  return 0;
}