BOJ 17828 : 문자열 화폐

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

17828번: 문자열 화폐

그리디로 쉽게 풀어줄 수 있다.

문제를 풀어 설명하자면 다음과 같다.

문자열 A~Z를 1~26이라고 했을 때, 이들을 모두 더한 것을 문자열 화폐라고 한다.

즉 AAABB 같은 경우 1+1+1+2+2 = 7

이때 길이 N이면서 가치는 M을 갖는 문자열을 구성하라는 것이다. 그러니까 위의 문자열은 N=5 M=7 일때의 정답이다.

 

이를 풀어주는 방법은 위에서 말한대로 그리디를 쓰면 된다.

• 길이 N만큼을 전부 A로 채우고
• 부족한 만큼 Z혹은 다른 문자로 채워나가면 된다.

이렇게 쓱 돌리면 싹 풀린다.

 

소스코드는 깃허브에 올려둠

https://github.com/onaeonae1/ProblemSovling/blob/master/BOJ%2017828.cpp

onaeonae1/ProblemSovling

*사실 아이디어에 비해 구현은 매우 지저분하게 한 게 아쉽다.