[GoLang] 백준 11726번, 11727번 2×n 타일링

개요

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

11726번: 2×n 타일링

 

2xn 직사가형을 2x1, 1x2 직사각형으로 채우기 문제입니다.

그림을 보면 매우 쉽게 풀 수 있던 문제입닌다.

 

일단 기본적으로 이전 거에서 1x2를 붙이는 것만으로 경우의 수가 어느 정도 정해졌습니다

그리고 또 알 수 있는 건 이전의 이전 거를 기준으로 2x2에 공간이 생겼는데

여기에도 2x1을 두개 넣은 2x2 정사각형을 붙임으로써 고유 경우의 수를 만들 수 있습니다

 

말로만 하면 그런가라는 생각이 들 수 있는데

아래 사진을 보면 파란 색 화살표는 2x2 추가 칸이 생길 경우의 수이고 빨간색 화살표는 1x2 추가 칸이 생길

경우의 수입니다.

 

위 사진은 2,3 수를 기준으로 4번째에 나올 경우의 수를 구한 것이죠

그러면 n번째 수의 식은 다음과 같습니다. 

# count가 전체 경우의 수를 담을 변수이고, i이 현재 순서라면
count[i] = count[i-1] + count[i-2]

 

어디선가 자주 본 익숙한 식입니다.

바로 피보나치입니다.

 

피보나치는 재귀로 구현할 경우 n 제곱의 시간 복잡도를 가집니다.

그렇기에 반복문과 배열로 처리하여 시간 복잡도가 낮게 하여 n으로 코드를 작성했습니다.

 

코드

문제에서 10007로 나눈 나머지를 출력하라고 했기에 나머지 연산을 추가했습니다.

package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscanln(reader, &n)

	var count = make([]int, n+1)
	for i := 1; i < n+1; i++ {
		if i == 1 {
			count[i] = 1
		} else if i == 2 {
			count[i] = 2
		} else {
			count[i] = (count[i-1] + count[i-2]) % 10007
		}
	}
	fmt.Fprintln(writer, count[n])
}

 

11727

이 문제도 11726이랑 동일합니다.

동일한대 단지 2x2가 추가된 것 입니다.

그러면 위 코드에서 바꿔야 될 것은 다음과 동일하게 됩니다.

• 2번째 단계에서 1이 추가되야 합니다. (2x2 추가로)
• 이전, 이전거에서 2x2 블록을 만드는 경우의 수가 추가되서 값이 2배가 됩니다.

코드는 다음과 같습니다

딱 2줄 바꾸면 해결됩니다.

 

package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscanln(reader, &n)

	var count = make([]int, n+1)
	for i := 1; i < n+1; i++ {
		if i == 1 {
			count[i] = 1
		} else if i == 2 {
			// 2 => 3으로 변경
			count[i] = 3
		} else {
			// 곱하기 2 추가
			count[i] = (count[i-1] + 2*count[i-2]) % 10007
		}
	}
	fmt.Fprintln(writer, count[n])
}