[Beakjoon Online Judge] 16440 - 제이크와 케이크

I 문제 소개

---

문제

제이크는 레이니콘으로부터 긴 모양의 케이크를 선물 받았습니다. 
케이크 위에는 N개의 과일 조각이 올려져 있는데 케이크 위에는 딸기 N/2개와 키위 N/2개가 일정한 간격을 두고 일렬로 올려져 있습니다. 여기서 N은 4의 배수입니다.
제이크는 케이크를 핀과 올려진 과일의 종류를 포함하여 케이크를 정확히 절반씩 먹기 위해 받은 케이크를 잘라서 나누어 가지려고 합니다. 이때 제이크가 받은 딸기가 N/4개여야 하며 키위도 N/4개 있어야 합니다. 핀도 제이크와 같은 개수의 딸기와 키위를 받아야 합니다.
제이크와 핀은 케이크를 자르기 귀찮으므로 그 횟수를 최소화하고자 합니다. 핀과 제이크가 똑같이 나누어 먹기 위해 케이크를 잘라야 하는 최소 횟수와 방법을 알려주세요.

 

입력

첫 번째 줄에는 케이크 위에 있는 과일의 개수 N (4 ≤ N ≤ 200,000) 이 주어집니다.
두 번째 줄에는 케이크의 정보가 담긴 길이가 N인 문자열이 주어집니다. i번째 문자가 's'이면 i번째 칸에는 딸기가 'k'이면 키위가 올려져 있음을 의미합니다.

 

출력

첫 번째 줄에 최소 횟수 k (1 ≤ k ≤ N - 1) 를 출력합니다.
두 번째 줄에는 k개의 정수 c1, c2, ..., ck (1 ≤ c1 < c2 < ... < ck  ≤ N - 1) 를 출력합니다. 여기서 ci는 ci 번째 과일이 있는 곳과 ci +1번째 과일이 있는 곳 사이를 자른다는 의미입니다.
자르는 방법이 여러 개인 경우 그 중 하나만 출력합니다.

---

II 문제 풀이

---

solved.ac 기준 플레티넘 4의 난이도인 문제다.

개인적인 견해로는 핵심만 짚는다면 정말 쉽게 풀 수 있고, 아마 푼 사람이 적어서 그렇지 푼 사람이 많다지면 난이도가 더 내려갈 것 같다.

 

이 문제는 고맙게도 딸기(s)와 키위(k)가 각각 총 N/2개로 정해져있고, 다른 과일은 없다. 그리고 이걸 N/4개씩 담게 만들면 된다. 그것도 최소 횟수로!

 

결론부터 말하자면, 과일이 두가지밖에 없는 이상 어떤 경우든 2번 이내에 해결할 수 있다.

다시 말해서, 길이가 N/2인 구간 중 딸기와 키위를 N/4개씩 담고있는 구간이 반드시 존재한다.

이것을 또 다시 말하면, 그 구간이 딱 절반이거나 그 구간 앞뒤로만 자르면 된다.

 

이렇게 조건이 많아져 생각해야하는 범위가 좁아지므로 코딩이 간단해졌다.

 

0. 초기 환경 설정

---

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int main(void)
{
	int N,s,k,i;
	string cake;
	queue<char> qcake;

	cin >> N;
	cin >> cake;
    
    return 0;
}

이 문제에 큐를 사용했다.

사실 큐를 활용하지는 못했으나, 뭔가 슬라이딩 윈도우가 생각나길래 큐를 만들어보았다.

슬라이딩 윈도우는 데이터 통신에서 데이터를 서버로 전송하고 받을 때 나오는 용어인데, 어디보자... 내 데통학점이..... 그만 알아보도록 하자.

어쨌든 미닫이 창문을 미는 모양을 따온 말이다.

그걸 구현하기 위해 큐를 사용했다. 왜냐면 선입선출(FIFO: First In First Out)의 특성을 갖기 때문이다.

사실 하나하나 세려고 이중 for문을 사용했는데 시간초과떠서 때려치고 큐에 저장하기로 했다.

 

1. 구간 탐색

---

s = k = 0;

for (i = 0;i < N;i++)
{
	qcake.push(cake[i]);

	if (qcake.back() == 's')
		s++;
	else
		k++;

	if (s > N / 4)
	{
		for (;qcake.front() != 's';)
		{
			qcake.pop();
			k--;
		}
		qcake.pop();
		s--;
	}
	else if (k > N / 4)
	{
		for (;qcake.front() != 'k';)
		{
			qcake.pop();
			s--;
		}
		qcake.pop();
		k--;
	}
	else if (s == N / 4 && k == N / 4)
	{
		break;
	}
}

s와 k는 각각 딸기의 개수와 키위의 개수를 세는 변수다.

그리고 앞에서부터 큐에 저장한다.

슬라이딩 윈도우의 모습이 되기 위해서는 처음 크기를 N/2로 고정해야겠으나, 그러려면 N/2만큼 따로 큐에 입력해야하는데 그게 귀찮아서 어차피 s와 k가 각각 N/4개씩 있을 때가 결국 크기가 N/2이므로 for문 하나로 처리했다.

만약 시간 초과가 일어났다면 이 부분부터 분리해서 미리 N/2만큼 계산했을 것이다.

 

그리고 딸기나 키위 중 N/4개가 넘어가면 그 구간은 이미 글러먹은 구간이므로 다음 구간으로 넘어가야한다.

이 때 한 개가 초과됐다고 해서 큐를 앞에서부터 한 개만 자르면 안된다.

딸기가 초과됐는데 그 구간의 맨 앞이 키위일수도 있기 때문이다.

따라서 딸기가 초과되면 딸기가 나올때까지 앞에서부터 키위를 자르고, 그 다음 딸기를 잘라야한다.

 

위 코드는 그에 대한 내용이다.

 

2. 구간 산정

---

int begin, end;
end = i+1;

if (end == N / 2)
	cout << 1 << endl << end;
else
{
	begin = end - N / 2;
	cout << 2 << endl << begin << " " << end;
}

구간의 앞과 뒤를 정해줄 begin과 end라는 변수를 만들었다.

1에서 s=N/4, k=N/4를 만족하는 구간을 찾은 순간의 i가 그 구간의 마지막 원소의 인덱스다.

따라서 구간의 끝이 i라고 할 수 있는데, 인덱스는 0부터 시작하고 문제에서는 1번째부터 시작하므로 1을 더했다.

 

이 end가 절반이라면, 한번 잘라서 만들 수 있다는 뜻이므로 출력 조건에 따라 1과 end만 출력한다.

절반이 아니라면, 반드시 두번 잘라서 만들 수 있다는 뜻이므로 출력 조건에 따라 2와 begin과 end를 출력한다.

이 구간의 길이는 무조건 N/2이기 때문에 begin은 end에서 N/2를 뺀 값이 된다.

 

3. 최종

---

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int main(void)
{
	int N,s,k,i;
	string cake;
	queue<char> qcake;

	cin >> N;
	cin >> cake;


	s = k = 0;
	for (i = 0;i < N;i++)
	{
		qcake.push(cake[i]);

		if (qcake.back() == 's')
			s++;
		else
			k++;

		if (s > N / 4)
		{
			for (;qcake.front() != 's';)
			{
				qcake.pop();
				k--;
			}
			qcake.pop();
			s--;
		}
		else if (k > N / 4)
		{
			for (;qcake.front() != 'k';)
			{
				qcake.pop();
				s--;
			}
			qcake.pop();
			k--;
		}
		else if (s == N / 4 && k == N / 4)
		{
			break;
		}
	}
	

	int begin, end;
	end = i+1;

	if (end == N / 2)
		cout << 1 << endl << end;

	else
	{
		begin = end - N / 2;
		cout << 2 << endl << begin << " " << end;
	}

	return 0;
}

문제의 난이도에 비해 굉장히 단순하고 쉬운 코드가 나왔다.

 

III 느낀점

---

최대 2번이라는 결론에 도달하는 데에 조금 오래 걸렸으나, 코드 짜기가 너무 편했다.

그러다가 '어 슬라이딩 윈도우 같은데?'라는 생각이 뇌리를 스쳤고, 바로 이어서 '...슬라이딩 윈도우가 뭐였더라'라는 생각이 들었다. 데통 조금만 더 열심히 할걸...

 

풀다가 생각난 문제인데, 과연 과일 개수가 4개라면 어떨까? 그러면 4번 이하로 잘라서 만들 수 있다.

과일 개수가 N개라도 사람이 두명이면 N번 이하로 잘라서 만들 수 있다.

 

그런데 과일 개수가 3개이고 사람이 3명이라면? 그때부터는 조금 복잡해질 것 같다.

어디까지나 두사람이 나눠서 가능한 정리였다.

 

개인적으로 자료구조나 알고리즘을 복잡하게 써서 푸는 문제가 싫어서

이런 문제들이 코테에 나오면 좋겠다고 생각한다. 물론 그럴 일은 없지만...

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 16440번 제이크와 케이크 C++

BOJ 16440번 제이크와 케이크 C++

백준 16440번 제이크와 케이크 C++