미소를뿌리는감자의 코딩
[백준 2024/02/28] 5705번 Hexagonal Tiles 본문
https://www.acmicpc.net/problem/5705
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)
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/03/19] 9184번 신나는 함수 실행 (0) | 2024.03.19 |
---|---|
[백준 2024/02/28] 1149번 RGB거리 (0) | 2024.02.28 |
[백준 2024/02/27] 2579번 계단 오르기 (0) | 2024.02.27 |
[백준 2024/02/26] 1956번 운동 (1) | 2024.02.26 |
[백준 2024/02/26] 1753번 최단경로 (0) | 2024.02.26 |