[백준] Moo 게임, [백준] 샤워실 바닥 깔기

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

5904번: Moo 게임

재귀

- 왼쪽, 가운데, 오른쪽 으로 나누어 재귀를 실행함.

import sys

def solution(n):
    
    def moo(s,idx, n):
        prev = (s-(idx+3))//2
        if n <= prev:
            return moo(prev, idx-1, n)
        elif n > (prev + idx + 3):
            return moo(prev, idx-1, n-prev-(idx+3))
        else:
            return "o" if n - prev-1 else "m"
    
    s, idx = 3,0
    while n > s:
        idx +=1
        s = s*2 + idx+3
    
    return moo(s,idx, n)


n = int(sys.stdin.readline())
print(solution(n))

 

 

 

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

14601번: 샤워실 바닥 깔기 (Large)

재귀

- 아래 그림과 같이 한변의 길이가 8인 정사각형에는 아래와 같이 재귀의 방법으로 타일을 깔수 있다. (배수구의 위치를 -1이라 가정)

- size//2 = 4 한번의 길이가 4인 영역(왼쪽위부터 시계방향으로)에서 1사분면에 -1이 없으면 1사분면에는 오른쪽하단에 타일

2사분면에 -1이 없으면 왼쪽하단에 타일, 3사분면에 -1이 없으면 오른쪽상단, 4사분면에는 -1이 있으므로 넘어간다

- 재귀방법으로 size // 2  과정을 반복해서 타일을 채워나가며 size = 2 -> break

import sys

def solution(k, x,y):
    def check(arr, size, x, y):
        for i in range(size):
            for j in range(size):
                if arr[y+i][x+j] == -1:
                    return False
        return True
    
    def tile(size, idx, arr, x, y):
        if size == 2:
            return arr
        n_size = size // 2
        if check(arr, n_size, x, y):
            arr[y+n_size-1][x+n_size-1] = idx
        if check(arr, n_size, x, y+n_size):
            arr[y+n_size-1][x+n_size] = idx
        if check(arr, n_size, y+n_size, x):
            arr[y+n_size][x+n_size-1] = idx
        if check(arr,n_size, x,y):
            arr[y+n_size][x+n_size] = idx
        idx +=1
        print(idx)
        tile(n_size, idx, arr, x,y)
        tile(n_size, idx, arr, x+n_size, y)
        tile(n_size, idx, arr, x,y+n_size)
        tile(n_size, idx, arr, x+n_size, y+n_size)
    
    n = 2**k
    arr = [[0 for _ in range(n)]for _ in range(n)]
    arr[-y][-x+1] = -1 #배수구 
    idx = 1
    
    
    
    
    return tile(n, idx, arr, 0,0)


k = int(sys.stdin.readline())
x,y = map(int, sys.stdin.readline().split())
answer = solution(k,x,y)
for row in answer:
    print(*row)