[백준/C++] 5525번: IOIOI(S2)

문제

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

5525번: IOIOI

 

사용한 알고리즘

2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)

-> Polynomial Rolling hash 

 

풀이

1. 부분 문자열 P를 정수 p로 바꿔준다.
2. 문자열 S의 첫번째 부분 문자열을 정수 num으로 바꿔준다.
3. num과 p가 같으면 정답을 1 증가시킨다.
4. S의 모든 부분 문자열을 정수 num으로 바꾸고 p와 비교해준다.
5. 정답을 출력한다.

 

 

 

소스코드

 

// WA code !!!

#include <iostream>
#include <cstring>
#include <cmath>

typedef long long ll;
using namespace std;

// Polynomial Rolling hash
#define X 27
// mod 사용 안함

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

    ll n,m; cin>>n>>m;
    // P의 길이는 2n+1, S의 길이는 m 이다.
    string S; cin>>S;
    ll ans=0; // S내의 P의 개수

    // 1. P를 정수 p로 바꿔준다
    ll p=0;
    for(int i=0; i<2*n+1; i++){
        if(i%2==0){
            p+= ll('I'-'A'+1)*(ll)pow(X,i);
        }
        else{
            p += ll('O'-'A'+1)*(ll)pow(X,i);
        }
    }

    // 2. S의 첫번째 부분 문자열을 정수 num으로 바꿔준다.
    ll num=0;
    for(ll i=0; i<2*n+1; i++){
        num += ll(S[i]-'A'+1)*(ll)pow(X,2*n-i);
    }
    // 3. num과 p가 같으면 정답을 1 증가시킨다.
    if(num==p) ans++;

    // 4. S의 모든 부분 문자열을 정수 num으로 바꾸고 p와 비교해준다.
    for(ll i=0; i<m-(2*n+1); i++){
        num -= ll(S[i]-'A'+1)*(ll)pow(X, 2*n);
        num *= X;
        num += ll(S[i+(2*n+1)]-'A'+1);
        if(num==p) ans++;
    }
    cout<<ans;
    return 0;
}

 

처음에 이렇게 풀었는데
한참을 맞왜틀을 했었다.
그러다가 pow()가 오차를 발생시킨다는 것을 알게되었다.

pow()를 MinGW 환경에서 컴파일 할 때 오차가 발생하는데,
백준에서 C++을 컴파일 할 때
이와 비슷한 g++ Main.cc -o Main -O2 -Wall -lm로 한다고 한다.

따라서 코드를 다음과 같이 수정하였다.

1줄요약 하자면,
pow()함수 대신에
for문을 돌며 POW변수에 X를 직접 곱해주는 방식으로 하였다.

 

#include <iostream>
#include <cstring>

typedef long long ll;
using namespace std;

// Polynomial Rolling hash
#define X 27
// mod 사용 안함

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

    ll n,m; cin>>n>>m;
    // P의 길이는 2n+1, S의 길이는 m 이다.
    string S; cin>>S;
    ll ans=0; // S내의 P의 개수

    // 1. P를 정수 p로 바꿔준다
    ll p=0;
    ll POW=1;
    for(int i=0; i<2*n+1; i++){
        if(i%2==0){
            p+= ll('I'-'A'+1)*POW;
        }
        else{
            p += ll('O'-'A'+1)*POW;
        }
        POW *= X;
    }

    // 2. S의 첫번째 부분 문자열을 정수 num으로 바꿔준다.
    ll num=0;
    POW=1;
    for(ll i=2*n; i>=0; i--){
        num += ll(S[i]-'A'+1)*POW;
        if(i) POW *= X;
    }
    // 3. num과 p가 같으면 정답을 1 증가시킨다.
    if(num==p) ans++;

    // 4. S의 모든 부분 문자열을 정수 num으로 바꾸고 p와 비교해준다.
    //POW /= X;
    for(ll i=0; i<m-(2*n+1); i++){
        num -= ll(S[i]-'A'+1)*POW;;
        num *= X;
        num += ll(S[i+(2*n+1)]-'A'+1);
        if(num==p) ans++;
    }
    cout<<ans;
    return 0;
}

 

참고로..
pow()를 round()함수로 감싸주면
오차를 어느정도 해결할 수 있지만, 

애초에 pow()함수는 실수 연산을 하기때문에
round()를 이용하여 반올림을 하더라도 오차가 발생할 수 있다.

따라서 굳이 실수를 사용하지 않아도 될 경우라면
pow()를 통한 실수 사용을 최대한 지양하는 편이 좋다!

(출처: 22W 신촌캠프 초급스터디 슬랙)

^^...