[백준 2024/02/28] 5705번 Hexagonal Tiles

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

5705번: Hexagonal Tiles

 

1. 접근 방법

이런 구성을 2차원 배열으로 만들 수 있지 않을까라고 생각하게 되었다. 

이런 식으로 2차원 배열로 만들 수 있었다.

 

(홀수)

3을 한번 봐보자, 3의 경우 1, 2, 4, 5로 이동할 수 있다.

하지만, 큰 수로만 이동이 가능하기 때문에, 4, 5로 이동할 수 있다. (오른쪽과, 오른쪽 대각선 아래)

 

이를 코드로 적어보면, 

find_cases(n + 1, x + 1, y + 1, num)
find_cases(n + 2, x, y + 1, num)

 

이동할 수 있는 방법이 2개 있다.

 

(짝수)

4를 한번 보면, 2, 3, 5, 6 으로 이동할 수 있다. 하지만, 큰 수로만 이동이 가능하기 때문에, 5, 6으로만 이동이 가능하다.

이를 코드로 적어보면,  (위와 오른쪽)

 

find_cases(n + 1, x - 1, y, num)
find_cases(n + 2, x, y + 1, num)

 

이런 경우의 수가 생기게 된다.

 

주어진 수가 12라고 가정했을 때,

재귀를 멈추게 되는 방법은, n이 12에 도달하거나, -> 유효한 case이므로 1 반환

 

n == -1에 도달하거나, y > (num//2) 인 경우이다. -> 유효하지 않은 case이므로 0 반환

 

이런식으로 코드를 작성하게 된다.

하지만, 이런식으로만 적으면 시간초과가 나게 된다. 

 

따라서 memoization을 이용해서 중복된 계산을 하지 않도록 할 것이다.

 

key = (n, x, y)라고 했을 때, 이것이 memo라는 dictionary에 값이 저장되어 있다면, 바로 그 값을 반환해 주었다.

 

만약 n이 memo에 저장된 값이 없다면, 해당 위치에서 생기는 경우의 수를 계산을 하고, 그 값을 memo에 갱신해 주었다.

추후에 똑같은 index에 접근하게 되면, 바로 그 값을 반환할 수 있도록 하였다.

 

2. 코드

import sys


def create_grid(n):
    grid = [[0 for _ in range(n // 2 + 1)] for _ in range(2)]

    for i in range(0, n + 1, 1):
        if i % 2 == 0:
            even_y = int(i / 2)
            grid[1][even_y] = i
        else:
            odd_y = int((i - 1) / 2)
            grid[0][odd_y] = i

    if n % 2 == 0:
        grid[0][int(n // 2)] = -1

    return grid


def find_cases(n, x, y, num):
    key = (n, x, y)
    if key in memo:
        return memo[key]

    if n == -1 or y > (num // 2):
        memo[key] = 0
        return 0

    if n == num:
        memo[key] = 1
        return 1

    if n % 2 == 0:
        result = find_cases(n + 1, x - 1, y, num) + find_cases(n + 2, x, y + 1, num)
    if n % 2 == 1:
        result = find_cases(n + 1, x + 1, y + 1, num) + find_cases(n + 2, x, y + 1, num)

    memo[key] = result
    return result


memo = {}
nums = []
total = 0
while True:
    line = sys.stdin.readline().strip()
    if not line:
        break
    num = int(line)
    if num == 0:
        break
    nums.append(num)

for num in nums:
    grid = create_grid(num)
    memo.clear()
    total = find_cases(0, 1, 0, num)
    print(total)