[ boj : 7913 ] Afternoon Tea

www.acmicpc.net/problem/7913

7913번: Afternoon Tea

문제 : 처음 찻잔에 우유 절반과 차 절반이 들어있습니다. 우린 엄격한 규칙에 의해 이 차를 마실 수 있는데 규칙은 이렇습니다.

1. 현재 들어있는 차의 절반을 마십니다.

2. i번째 문자가 'H' 라면 '차'를 가득찰때까지 붓습니다.

   i번째 문자가 'M' 이라면 '우유'를 가득찰때까지 붓습니다.

이것을 반복합니다. 단, 마지막 액체(우유,차 중 하나)를 가득 부은 건 버립니다.

 

해설 : 이 문제 일단 전 도움을 받았습니다.(감사합니다)

너무 어려웠습니다. 수학광들은 보자마자 식 세우고 슥삭 한다던데 전 멍청이라 절대 안되더군요.

바로 해설 들어가겠습니다.

 

먼저 처음에는 1/2 우유, 1/2 차가 들어있고 각 단계마다 절반마시고 가득 채우고 이 행동을 반복하게 되겠죠.

그래서 맨 마지막까지 어떤 종류의 마실것을 더 많이 마셨는지 구하면 그게 정답입니다. 그러나 총 10만 길이의 문자열이 주어지니 우린 매 문자마다 행동을 하고 결과값을 더해서 도출할 수가 없습니다. (파이썬을 이용해도 이 방식은 tle가 발생할 겁니다)

 

방법을 달리해봅시다. '먹는 양'에 집중하지말고 반대로 '못 먹는양'에 집중을 해보도록 해봅시다.

맨 마지막 문자는 굳이 신경써줄 필요가 없겠죠. 어차피 마시는게 아닌 '버리게' 되니까요.

 

(지금부터 맨마지막 문자는 진짜 맨 마지막 문자에서 바로 앞 문자로 지칭하겠습니다.)

매번 절반을 마시고 절반의 마실것(우유,차)를 채우게 됩니다. 이 뜻은 현재 내가 마실 것 중 하나(우유,차)를 채울때 1/2의 양을 채우게 되는 것 입니다. 조건을 주고 시작하면 '마실 것'을 넣는 양은 항상 1이라고 가정하겠습니다.

 

맨 마지막 문자를 생각해 봅시다. (그 전에 어떤 마실 것이 들어있는지 어떤 행동을 했는지 생각 조차 하지 마시고 지금 문자의 행동에만 생각하세요)

현재 찻잔에는 1/2의 빈 공간이 존재합니다. 여기에 어떤 '마실것(우유,차)' 를 넣고 나서 섞여질때까지 휘저어 줍니다. 그리고 나서 '절반'을 마시게 됩니다. 그러면!!기존에 들어있는 액체는 생각하지 말고 방금 넣은 '마실 것' 만 생각해 보았을때 1의 양을 넣었고 절반을 마시게 되고 절반을 버리게 되었으니 1/2의 양을 버리게 됩니다.

 

이 전 단계를 생각해 봅시다.(이때도 전에 행동을 생각하지도 마세요)

역시 마찬가지로 현재 1/2의 빈 공간이 있고 여기에 1의 양인 '마실것'을 넣습니다. 그리고 나서 절반을 마시고 절반은 남기게 되겠죠. 그럼 1/2의 양을 마시게 되고 1/2의 양을 남기게 됩니다.

이 이후의 단계가 되었을때는 1/2의 양이 남아 있는 '마실 것'에서 또 다시 절반을 마시게 됩니다. 이 단계는 마지막 단계가 되니 절반을 버리게 되겠죠. 즉, 1/2의 1/2인 1/4의 양을 마시고 1/4을 버리게 되는 것 입니다.

그럼 지금까지 1/2 + 1/4 의 양을 마시고 1/4의 양을 버리게 됩니다.

 

또다시 이 전 단계를 생각해보면 결국 1/2 + 1/4 + 1/8 의 양을 마시게 되고 1/8의 양을 버리게 된다는 것을 알 수 있습니다.

 

자, 그럼 우린 어떤 '마실 것'을 얼만큼 버리게 되는지 알게 되었습니다. 그러면 우유와 차 중 어떤 마실것을 더 많이 버리게 되는지 알면 답을 구할 수 있게 됩니다.

 

결국 버리게 되는 양은 1/2 + 1/4 + 1/8 ~~~ 이 되겠죠. 이 수들의 합은 절대로 1을 넘지 않습니다. 

이 말이 곧 무슨 뜻이냐면 결국 우유와 차 중 단 한번이라도 더 많이 찻잔에 붓게 된다면 그 마실것이 정답이 된다는 뜻입니다. 이해가 잘 안가시죠?

 

우린 이미 위에서 추가하는 양을 1로 정의를 해놓았습니다. 

만약 차를 3번, 우유를 4번 추가한다고 생각해 보면 차를 마실 수 있는 양은 2<x<=3 이고, 우유를 마실 수 있는 양은 3<y<=4 입니다. 왜냐???3번의 차를 가득 채웠고 여기서 못마신 양을 빼줘야 하는데 못마시는 양은 아무리 많이 더해도 1을 넘길 수 없으니 결국 2<x<=3 의 범위 안에 존재하게 되는 것이죠... 우유도 마찬가지고요. 그래서 결국 하나라도 더 많이 가득 채운 쪽이 정답이 되는 것 입니다.

 

그렇다면 만약 우유와 차가 동일한 횟수를 가지게 된다면 어떻게 되는 것 일까요?

우린 맨 마지막에 버리는 양이 1/2 라고 위에서 알 수 있었습니다. 그러면 이 전까지 아무리 다른 마실것을 안먹더라도 1/2의 이상의 값이 나올 수 있을까요???

더 쉽게 설명하면 맨마지막에 '차'를 가득붓고 1/2의 양을 버렸습니다. 근데 이전까지 계속 '우유'만 가득 채웠다고 하면 우유를 마시지 않은 양은 1/4 + 1/8 + 1/16 ~~~ 이 됩니다. 이 합은 절대로 1/2를 넘을 수가 없는 것이죠.

 

그래서 동일한 횟수가 카운트 되었을때는 결국 맨 마지막 문자의 상대 마실것이 정답이 되는 것입니다.

 

n=1 일때는 따로 예외처리 해주셔야 되고요.

정말 어려웠던 문제입니다. 창의적으로 생각해야 했던 문제이기도 하고요. 부디 다들 잘 이해했으면 좋겠네요ㅠㅠ

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n;
	string s;
	cin >> n >> s;
	int x = 0, y = 0;
	
	for (int i = 0; i < s.length()-1; i++) {
		if (s[i] == 'H')x++;
		else y++;
	}
    if (n == 1) 
		cout << "HM";
	else if (x == y) {
		if (s[s.length() - 2] == 'H')cout << 'M';
		else cout << 'H';
	}
	else {
		if (x < y)cout << 'M';
		else cout << 'H';
	}
	return 0;
}