CODEFESTIVAL_2016_QUALA_C - Next Letter

[zeikar]

Problem link

https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_c

Problem Summary

문자열과 k가 주어진다. k번 연산을 통해 만들 수 있는 사전 순으로 가장 작은 수를 구하는 문제.
연산: 다음 문자로 변경, 단 z는 a로 변함.

Solution

일단 그리디 적으로 생각해보면

• 사전 순으로 최소가 되려면 앞 문자를 최대한 a로 만들어야 한다.
• a로 만들 수 없으면 아예 연산을 안 하는 것이 낫다.

위 두 규칙에 맞게 문자열을 돌면서 계산해주면 된다. 단, 연산 횟수가 남았을 경우 맨 마지막 문자를 수정하면 사전 순으로 최소가 되게 할 수 있다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s;
	int k;
	cin >> s >> k;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'a')
		{
			continue;
		}

		int diff = 26 - (s[i] - 'a');
		// possible to change to a
		if (k >= diff)
		{
			s[i] = 'a';
			k -= diff;
		}
	}

	// remains
	s[s.size() - 1] = ((s[s.size() - 1] - 'a') + k % 26) % 26 + 'a';

	cout << s << endl;
}