1️⃣ 문제

문제 - 모음사전

풀이 참조 - 블로그

구현은 어렵지 않은데 규칙을 생각하려니 머리 쪼개지는 문제였다 ..

그래서 dp는 점화식 찾는게 쉽지 않네 흑흑

2️⃣ 풀이 방법 및 코드

말 그대로 규칙을 찾는 것이 관건인 문제!

다른 풀이를 참조해도 이해하느라 애먹었다.. 직접 조합 하나 하나 써가면서 끄적여야 이해가 되더라 ^^!

1️⃣ 그래서 규칙이 무엇?

아래처럼 각 자리수마다 다음 알파벳이 바뀔 때마다 저만큼 수가 차이가 나는데 이게 어떻게 나왔냐면

5 자리) @@@@A -> @@@@E -> @@@@I -> @@@@O -> @@@@U		// 1씩 증가
4 자리) @@@A -> @@@E -> @@@I.... // 6씩 증가
3 자리) @@A -> @@E -> @@I.... // 31씩 증가
2 자리) @A -> @E -> @I.... // 156씩 증가
1 자리) A->E->I.... // 781씩 증가

자리 수가 높아질 때 마다 (x5) + 1만큼 커지는 규칙이다!

(입출력 예에서 A는 1이고, I는 1563인 것에서 두 알파벳 간의 차이는 1562이니까 E는 절반인 781인 것으로 접근해서 규칙 찾을 수도 있음!)

2️⃣ 규칙의 원리

그렇다면 왜 5를 곱하고 1을 더할까?

5는 모음의 갯수이고, 마지막 1을 더하는 이유는 해당 자리에 공백이 오는 경우(그 경우가 딱 한번이라서 그래서 곱한 후 한번만 더 하는거)를 더하기 때문이다!

3️⃣ 코드

A=0 , E=1 , I = 2 , O=3 , U =4라고 가정하고 자릿수 차이에 곱하여 더해주면 답 구할 수 있다.

answer를 word의 길이만큼 초기화해주는 이유는 길이별 A, AA, AAA, AAAA, AAAAA를 시작점으로 차이 만큼을 더해주기 때문!

import Foundation

func solution(_ word:String) -> Int {
    let vowelDict = ["A": 0, "E": 1, "I": 2, "O": 3, "U": 4]
    // 자릿수가 바뀔 때마다 (*5 + 1)만큼 바뀜
    var diff = (((1 * 5 + 1) * 5 + 1) * 5 + 1) * 5 + 1      // 781
    var answer = word.count
    
    for w in word {
        answer += diff * vowelDict[String(w)]!
        diff = (diff - 1) / 5   // 다음 자릿수 만큼 차이 줄이기 (규칙의 역계산)
    }
    return answer
}

3️⃣ 이 문제를 풀면서 되새긴 점

DP 문제 많이 풀어서 감 익히자 ㅎㅎㅎㅎㅎㅎ