2 x N 바닥을 채울 수 있는 1x1, 1x2, 2x1 타일의 가능한 조합 수를 계산하는 방법은 무엇입니까?-Golang-php.cn

2 x N 바닥을 채울 수 있는 1x1, 1x2, 2x1 타일의 가능한 조합 수를 계산하는 방법은 무엇입니까?

WBOY

풀어 주다： 2024-02-10 08:54:08

앞으로

460명이 탐색했습니다.

如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x N 地板？

php 편집자 Xinyi는 모두를 위한 흥미롭고 두뇌를 자극하는 질문에 답할 것입니다. 1x1, 1x2, 2x1 타일의 가능한 조합이 2 x N 바닥을 채울 수 있는 수는 어떻게 계산할 수 있습니까? 이 문제에는 조합수학과 동적 프로그래밍에 대한 지식이 필요하며, 분석과 도출을 통해 간단하고 효과적인 계산 방법을 생각해 낼 수 있습니다. 다음으로, 이 질문에 대한 답을 함께 살펴보겠습니다!

질문 내용

방금 기술 테스트를 했는데 이 작업에 대해 혼란스러워요. 나의 목표는 이 "덮인 바닥" 문제를 해결하는 방법을 이해하는 것입니다. 솔직히 어디서부터 시작해야할지 모르겠습니다.

미션은:

2xn 레이어가 있습니다.
바닥을 채울 수 있는 1x1, 1x2, 2x1 타일이 있습니다.

질문은:

solution(1) 예상 출력은 2, 실제 출력은 2입니다.
그러나 solution(2) 예상 출력은 7이고 실제 출력은 3입니다.

현재 해결 방법은 다음과 같습니다.

1x1은 항상 2xn 레이어를 채울 수 있으므로 가능한 방법은 1부터 시작됩니다.
남은 층수 모드 2가 0이면 가능한 길은 1씩 증가합니다.

현재 솔루션의 문제점은 1x2 블록과 2x1 블록을 구분하지 않는다는 것입니다. 따라서 solution(2)의 경우 실제 출력은 7이 아닌 3입니다.

코드

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
    possibleWays := 1

    floorArea := 2 * n
    // Your code starts here.

    for i := floorArea - 1; i >= 0; i-- {
        residualFloorArea := floorArea - i
        fmt.Println(i, residualFloorArea)
        if residualFloorArea%2 == 0 {
            fmt.Println("punch")
            possibleWays += 1
        }
    }

    return possibleWays
}

func main() {
    fmt.Println(Solution(1))
    fmt.Println("next")
    fmt.Println(Solution(2))
}

로그인 후 복사