취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 29812번 문제인 아니 이게 왜 안 돼이다.
문제는 아래 링크를 확인하자.

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

이 문제는 두 작은 문제를 해결해야 한다. 하나는 'H', 'Y', 'U'가 아닌 모든 문자를 지우는 데에 필요한 에너지의 최솟값을 구하는 것이고 다른 하나는 만들 수 있는 "HYU"의 개수를 구하는 것이다. 두 번째 문제의 경우 'H', 'Y', 'U' 중 가장 적은 문자의 개수만큼은 "HYU"를 항상 만들 수 있지만 그보다 많은 개수는 항상 만들 수 없다는 점을 관찰해 쉽게 해결할 수 있다. 아래에서는 첫 번째 문제의 해결 방법을 살펴보자.

지워야 하는 두 문자 사이에 'H', 'Y', 'U'가 끼어있으면 해당 두 문자를 드래그로 같이 선택해 지울 수 없다는 점을 확인하자. 따라서 주어지는 문자열을 'H', 'Y', 'U'을 기준으로 잘라 얻을 수 있는 각 부분문자열을 지우는 에너지의 합을 구하는 것으로 문제의 답을 구할 수 있다.

모든 문자가 지워야 할 문자일 때 드래그를 두 번 이상 하고 지우는 것은 모든 문자를 한 번에 드래그하고 지우는 것보다 항상 많은 에너지가 든다는 점을 관찰하자. 따라서 최소 에너지를 구할 때 드래그는 많아야 한 번만 할 수 있다고 가정해도 문제의 답을 충분히 구할 수 있다. 드래그를 하는 경우와 하지 않는 경우의 에너지 사용량을 각각 구해 문제를 해결하자.

두 작은 문제 모두 답이 0인 경우 0이 아닌 문제에 주어진 문자열을 출력해야 하는 점을 유의하자.

아래는 제출한 소스코드이다.

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

int N, D, M;
string s;
int cnt[128], combo;
int ans;

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

	cin >> N >> s >> D >> M;
	for (auto &l : s) {
		if (l == 'H') {
			cnt['H']++;
			ans += min(M + D, combo * D);
			combo = 0;
		}
		else if (l == 'Y') {
			cnt['Y']++;
			ans += min(M + D, combo * D);
			combo = 0;
		}
		else if (l == 'U') {
			cnt['U']++;
			ans += min(M + D, combo * D);
			combo = 0;
		}
		else combo++;
	}
	ans += min(M + D, combo * D);

	if (ans) cout << ans << '\n';
	else cout << "Nalmeok\n";
	ans = min(cnt['H'], min(cnt['Y'], cnt['U']));
	if (ans) cout << ans;
	else cout << "I love HanYang University";
}