class Solution {
static final String ALPHABETS = "AEIOU";
static final int[] RATE_OF_INCREASE = {781, 156, 31, 6, 1};
public int solution(String word) {
int answer = word.length();
for (int i = 0; i < word.length(); i++) {
answer += (RATE_OF_INCREASE[i] * ALPHABETS.indexOf(word.charAt(i)));
}
return answer;
}
}
순수하게 완전탐색도 가능하지만, 규칙을 찾아 DP 로 해결할 수 있었음
규칙을 찾기위해 하나하나 나열해 가다보면 다음과 같은 규칙을 찾을 수 있음
x 가 0이 아닐 때 : f(x) = f(x - 1) + 5^x
f(0) = 1
f(1) = 1 + 5^1 = 6
f(2) = 6 + 5^2 = 31
f(3) = 31 + 5^3 = 156
f(4) = 156 + 5^4 = 781