CODEFESTIVAL_2016_QUALA_C - Next Letter #35
Description
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;
}