문제
구식 휴대폰 키패드(숫자 2~9)로 영문 메시지를 입력할 때 필요한 최소 버튼 누름 횟수를 구하는 문제이다.
각 버튼은 연타로 문자를 입력하며, 같은 버튼에 있는 문자를 연속 입력할 경우 w초의 대기 시간이 필요하다.
버튼 누름 비용은 p이며, 대기 비용은 w이다.
입력
첫째 줄에 버튼 누름 비용 p와 대기 비용 w가 주어진다. 둘째 줄에 대문자 알파벳과 공백으로 구성된 메시지가 주어진다. (공백 입력 비용은 p)
출력
메시지를 입력하는 데 필요한 총 비용을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 3 A BC | 9 |
풀이
각 문자의 키패드 위치와 연타 횟수를 사전에 배열로 정의하여 순차적으로 비용을 누적하는 구현 문제이다.
AL[26]배열: 각 알파벳을 입력하는 데 필요한 버튼 누름 횟수(연타 수)를 저장한다. (S, Z는 4회, 나머지 3회 이하)BTN[26]배열: 각 알파벳이 위치한 버튼 번호(2~9)를 저장한다.- 문자열을 순회하며 공백이면
p를 더하고, 알파벳이면p * AL[n]을 더한다. - 직전 입력과 같은 버튼 번호이고, 공백이 아니었다면 대기 비용
w를 추가로 더한다.
핵심 아이디어: 직전 버튼 번호(pre_btn)를 추적하여 같은 버튼 연속 입력 여부를 판별하고 대기 비용을 선택적으로 적용한다.
코드
#include <iostream>
#include <string>
using namespace std;
int AL[26] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};
int BTN[26] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9};
int p, w;
string s;
int pre_btn;
int ans;
void init()
{
ans = 0;
pre_btn = 0;
}
void input()
{
cin >> p >> w;
cin.ignore();
getline(cin, s);
}
void solve()
{
for (int i = 0; i < s.size(); i++)
{
if (s[i] == ' ')
{
ans += p;
pre_btn = 1;
continue;
}
int n = s[i] - 'A';
if (n >= 0 && n <= 25)
{
ans += p * AL[n];
if (i != 0 && BTN[n] == pre_btn && pre_btn != 1)
{
ans += w;
}
pre_btn = BTN[n];
}
}
}
int main()
{
init();
input();
solve();
cout << ans << "\n";
return 0;
}복잡도
- 시간: O(N) (N: 메시지 길이)
- 공간: O(1)