백준 10096 (C++) 세 친구

최초 업로드: 2025-07-23 18:38:18

최근 수정 시간: 2025-07-23 18:38:41

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 세 친구

[문제 링크](https://www.acmicpc.net/problem/10096)

## 문제 설명

<img alt="" src="https://upload.acmicpc.net/7c16b9a4-a064-4998-b77f-b08892963bdf/-/preview/" style="width: 162px; height: 100px; float: right;">준규, 해빈, 진욱이는 다음과 같은 게임을 한다.

먼저, 준규가 문자열 S를 고른다. 그 다음, 해빈이는 S의 뒤에 S를 붙인 새로운 문자열 T를 만든다. 마지막으로 진욱이는 문자열 T의 어딘가(시작이나 끝도 가능)에 문자 하나를 삽입해 문자열 U를 만든다.

U가 주어졌을 때, S를 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 U의 길이 N이 주어지고, 둘째 줄에 U가 주어진다. U는 알파벳 대문자로만 이루어져 있다.

## 출력

<ol>
	<li>U를 만들 수 없는 경우에는 "<code>NOT POSSIBLE</code>"을 출력한다.</li>
	<li>U를 만들 수 있는 문자열 S가 유일하지 않다면, "<code>NOT UNIQUE</code>"를 출력한다.</li>
	<li>나머지 경우에는 S를 출력한다.</li>
</ol>

## 풀이
#### n/2, n/2+1와 n/2+1, n/2의 문자열로 각각 나누어 예외처리를 해주었다. 문자열 S가 존재하려면 앞의 절반 또는 뒤의 절반에 항상 매칭되기 때문에 항상 성립한다.

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

int n; string s;

bool match(int l1, int r1, int l2, int r2) {
 while(l1<=r1 && l2<=r2) {
 if(s[l1]==s[l2]) l1++;
 l2++;
 }
 return l1>r1;
}

bool isSame(int l1, int r1, int l2, int r2) {
 while(l1<=r1) {
 if(s[l1++]!=s[l2++]) return false;
 }
 return true;
}

void solve() {
 if(n%2==0) {
 cout << "NOT POSSIBLE";
 return;
 }

bool chk1 = match(0, n/2-1, n/2, n-1);
    bool chk2 = match(n/2+1, n-1, 0, n/2);

if(chk1 && chk2) {
 if(isSame(0, n/2-1, n/2+1, n-1)) {
 for(int i=0;i<n/2;i++) cout << s[i];
 } else {
 cout << "NOT UNIQUE";
 }
 } else if(chk1) {
 for(int i=0;i<n/2;i++) cout << s[i];
 } else if(chk2) {
 for(int i=n/2+1;i<n;i++) cout << s[i];
 } else {
 cout << "NOT POSSIBLE";
 }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    solve();
}
```