백준 2011번: 암호코드

❓ 문제

2011번: 암호코드

⌨️ 전체 코드

package main

import (
	"fmt"
	"strconv"
)

const DIVISOR = 1000000

var memo = map[string]int{}

func main() {
	input := ""
	fmt.Scan(&input)

	answer := getCombinations(input) % DIVISOR

	fmt.Println(answer)
}

func getCombinations(str string) int {
	if _, ok := memo[str]; ok {
		return memo[str] % DIVISOR
	}
	if len(str) == 0 {
		memo[str] = 1
		return memo[str] % DIVISOR
	}
	if string(str[0]) == "0" {
		memo[str] = 0
		return memo[str] % DIVISOR
	}
	if len(str) == 1 {
		memo[str] = getCombinations(str[1:])
		return memo[str] % DIVISOR
	}
	converted, _ := strconv.Atoi(str[0:2])
	if 10 <= converted && converted <= 26 {
		memo[str] = getCombinations(str[1:]) + getCombinations(str[2:])
		return memo[str] % DIVISOR
	}
	memo[str] = getCombinations(str[1:])
	return memo[str] % DIVISOR
}

💡 풀이

• 다이나믹 프로그래밍으로 풀면 된다.
  • 나는 Top-Down 방식으로 풀었다.
• 점화식: D[i] = D[i+1] + D[i+2] (i는 암호의 index)
• 메모이제이션을 하지 않으면 시간 초과가 나므로 이미 계산한 암호는 재사용하여 시간을 단축했다.
• 암호의 앞 두글자가 영어로 변환될 수 있을 때는 D[i] = D[i+1] + D[i+2]이지만 변활될 수 없다면 D[i] = D[i+1]이다.
• 문제의 예시를 들어 설명하자면 D(25114) = D(5114) + D(114) = 6 D(5114) = D(114) = 3 D(114) = D(14) + D(4) = 3 D(14) = D(1) + D(4) = 2 D(1) = 1 D(4) = 1
  

📖 새롭게 배운 내용

• 다이나믹 프로그래밍 구현 방법

💫 헷갈리는 부분

• 마지막 답만 문제의 조건대로 1,000,000으로 나누었는데 계속 틀렸다고 해서 삽질을 오지게 했다.
  • 다른 답들을 보니까 재귀함수 속에서도 계속 저 수로 나누길래 혹시나 하는 마음에 return 값을 다 나누었더니 맞았단다. 웃긴 건 게시판에 있던 모든 예시들 다 시도해봤는데 틀렸다고 한 답이 다 맞았다고 해서 다른 게 뭔지...;

📚 참고 자료

알고리즘 - Dynamic Programming(동적 계획법)