[그리디 #17] BOJ 21314 - 민겸 수

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

21314번: 민겸 수

 

 

접근 방법

두를 최종적으로 계산하는 경우는 두가지 이다.

 

1. K가 왔을때

2. string이 끝날때

 

이 두 가지 경우는 최소와 최대 공통적으로 적용된다.

 

이제 세부적으로 최대와 최소를 구하는 알고리즘을 생각해보자.

 

i) 최대

MKKMMK 의 경우, MK + K + MMK = 50 5 500 이다.

K는 50을 곱해버리므로 무조건 M과 붙어야한다.

 

따라서, 알고리즘은 다음과 같다.

 

1. M이 왔을 경우, mCnt를 +1 한다.

2. K일 경우, mCnt를 이용하여 수를 계산 후 결과 string에 붙인다.

3. string의 마지막 일 경우는 M이 마지막으로 오는 경우 밖에 없으므로 mCnt로 계산 후 결과 string 붙인다.

 

 

ii) 최소

MKKMMK 의 경우, M + K + K + MM + K = 1 5 5 10 5 이다.

K는 무조건 단독적으로 사용되고, M은 연속으로 올 경우 다 더해버린다.

 

따라서, 알고리즘은 다음과 같다.

 

1. M 다음이 K일 경우, mCnt로 계산한다.

2. M 다음이 K가 아닐 경우, mCnt를 +1 한다.

3. K 일 경우, 단독적으로 사용되므로 5를 붙인다.

 

 

알고리즘은 쉽게 생각할 수 있지만, 실수한 부분이 바로 자료형이다.

나는 계산할 때, long long을 이용하여 직접 계산하는 방법을 사용했다.

그러나, 값의 범위가 워낙커서 쓰레기값이 출력되었다.

 

따라서, vector<char> 에 수를 넣는 방식을 사용하였다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>

#define MAX 1010
#define INF 987654321

using namespace std;

string str;
vector<char> res1;
vector<char> res2;

int check(int mCnt, bool k) {
	if (mCnt == 1 && !k)
		return 0;
	else
		return mCnt;
}

void toString(vector<char>& res, string temp) {
	for (int i = 0; i < temp.length(); i++)
		res.push_back(temp[i]);
}

void calc(vector<char>& res, int mCnt, bool k, bool last) {
	if (k) {
		res.push_back('5');
		if (mCnt > 0) {
			res.push_back('0');
			for (int i = 0; i < mCnt - 1; i++)
				res.push_back('0');
		}
		
	}
	else {
		if (last) {
			for (int i = 0; i < mCnt; i++) {
				res.push_back('1');
			}
		}
		else {
			res.push_back('1');
			for (int i = 0; i < mCnt - 1; i++)
				res.push_back('0');
		}
		
	}
}

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

	cin >> str;

	// 최대
	int mCnt = 0;
	for (int i = 0; i < str.length(); i++) {
	
		if (str[i] == 'M')
			mCnt++;

		if (str[i] == 'K') {
			calc(res1, mCnt, true, false);
			mCnt = 0;
		}
		else if (i == str.length() - 1) {
			calc(res1, mCnt, false, true);
		}
	}

	// 최소
	mCnt = 0;
	for (int i = 0; i < str.length(); i++) {

		if (str[i] == 'M')
			mCnt++;

		if (str[i] == 'K') {
			calc(res2, mCnt, true, false);
			mCnt = 0;
		}
		else if (i == str.length() - 1) {
			calc(res2, mCnt, false, false);
		}
		else if (str[i] == 'M' && str[i + 1] == 'K') {
			calc(res2, mCnt, false, false);
			mCnt = 0;
		}
	}

	for (int i = 0; i < res1.size(); i++)
		cout << res1[i];
	cout << "\n";
	for (int i = 0; i < res2.size(); i++)
		cout << res2[i];
}