[PS / Go] 백준 11729 번 하노이 탑 이동 순서, 프로그래머스 타겟 넘버

백준 11729 번 하노이 탑 이동 순서

문제

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

풀이

하노이의 탑 이동 공식

1. 3개의 지점 from, to, via가 있고 n개의 원판이 from에 꽂혀 있을 때, n-1개의 원판을 from에서 to를 거쳐 via로 이동시킵니다. (a_n-1회)
2. n번째 가장 큰 원판을 to로 이동시킵니다. (1회)
3. 1에서 via로 이동시킨 n-1개의 원판을 via에서 from을 거쳐 to로 이동시킵니다. (a_n-1회)

이를 점화식으로 표현하면 a_n = 2 * a_n-1 + 1입니다.  a₁이 1이므로 또 다른 형태로 표현해 보자면 an = 2^n - 1이 되고, 이를 통해 n개의 원판의 이동 횟수를 구할 수 있습니다.

 

이동 순서는 n번째 원판을 이동하기 전에 n-1개의 원판을 이동시켜야 하므로 재귀를 사용하여 이동시키되, base case를 명시하여 영원히 탈출할 수 없거나 스택 오버플로우가 발생하지 않도록 주의해야 합니다. n-1번째 원판부터 파고 들어가야하기 때문에 탈출 조건은 n이 1인 경우, 가장 작은 원판을 이동시키는 경우가 될 것입니다. 가장 작은 원판은 from에서 to로 바로 이동시킵니다. 이 때 n이 짝수이면 to는 2번째 봉이 되고, n이 홀수이면 to는 3번째 봉이 된다는 규칙이 존재합니다.

코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	scanner = bufio.NewScanner(os.Stdin)
	writer  = bufio.NewWriter(os.Stdout)
	N       int
)

// 11729번: 하노이 탑 이동 순서
// hhttps://www.acmicpc.net/problem/11729
// 난이도: 골드 5
// 메모리: 864 KB
// 시간: 124 ms
// 분류: 재귀
func main() {
	defer writer.Flush()
	scanner.Split(bufio.ScanWords)

	Setup()
	Solve()
}

func Setup() {
	N = scanInt()
}

func Solve() {
	fmt.Fprintln(writer, 1<<N-1)
	towerOfHanoi(N, 1, 3, 2)
}

func towerOfHanoi(n int, from, to, via int) {
	if n == 1 {
		fmt.Fprintln(writer, from, to)
		return
	}

	towerOfHanoi(n-1, from, via, to)
	fmt.Fprintln(writer, from, to)
	towerOfHanoi(n-1, via, to, from)
}

func scanString() string {
	scanner.Scan()
	return scanner.Text()
}

func mustParseInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func scanInt() int {
	return mustParseInt(scanString())
}

---

프로그래머스 타겟 넘버

문제

프로그래머스

풀이

 dfs로도 풀 수 있는데 이 경우는 시간 복잡도가 최대 2²⁰인 반면, 반복문과 메모이제이션을 통해 문제를 풀면 시간 복잡도가 n * m (n: numbers의 최대 길이 20, m: 만들어질 수 있는 값의 범위의 크기 2000)이므로 더 빠른 시간 안에 문제를 해결할 수 있습니다.

테스트 케이스 1 비교

• dfs: (10.21ms, 3.73MB)
• dp: (0.16ms, 3.73MB)

코드

package main

func solution(numbers []int, target int) int {
	// 만들어질 수 있는 값의 범위는 -1000 ~ 1000 인데,
	// 배열의 인덱스는 0부터 시작하므로 음수를 처리하기 위해 1000을 더해준다.
	dp := make([][2001]int, len(numbers)+1)
	// 시작점을 0으로 설정 (0을 만들기 위한 경우의 수는 1이다.)
	dp[0][1000] = 1

	// 모든 숫자를 순회하며 경우의 수를 계산한다.
	for i := 0; i < len(numbers); i++ {
		// i번째 숫자를 더하거나 빼기 전의 경우의 수를 순회한다.
		for j := 0; j < 2001; j++ {
			// j를 만들 수 있는 경우의 수가 없다면 다음으로 넘어간다.
			if dp[i][j] == 0 {
				continue
			}

			// i번째 숫자를 더하거나 빼서 만들 수 있는 경우의 수를 갱신한다.
			dp[i+1][j+numbers[i]] += dp[i][j]
			dp[i+1][j-numbers[i]] += dp[i][j]
		}
	}

	// numbers의 모든 숫자를 사용하여 target을 만들 수 있는 경우의 수를 반환한다.
	// target이 음수일 수 있으므로 배열의 인덱스를 맞추기 위해 1000을 더해준다.
	return dp[len(numbers)][target+1000]
}

func main() {
	println(solution([]int{1, 1, 1, 1, 1}, 3)) // 5
}