BOJ 15551 : if 3

• 문제 링크 : boj.kr/15551
• 난이도 : G3
• 태그 : 해싱

15551번: if 3

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    for(int i = 0; i < n-2; i++) cout << "A";
    cout << "Ab\n";
    for(int i = 0; i < n-2; i++) cout << "A";
    cout << "BC";

    return 0;
}

---

풀이

문제의 핵심은 JAVA의 hashCode가 어떤 값을 반환하는지 아는 것이다. JAVA의 hashCode는 다음 값을 반환한다.

$$\sum_{i=0}^{n-1} {s[i] \times 31^{(n-1)-i}}$$

여기서 주목할 부분은 문자열의 마지막 두 부분이다. 이 부분만 따로 떼어서 보면 다음과 같다.

$$s[n-2] \times 31 + s[n-1]$$

이 값이 서로 같게 되는 두 자리 문자열을 찾으면 된다.

n이 2 이상일 경우 아무 같은 문자열을 각각의 앞에 혹은 뒤에 이어서 붙여주면 된다.