[BaekJoon] 백준 1074번 Z (Python)

[BaekJoon] 백준 1074번 Z

 

문제: https://www.acmicpc.net/problem/1074

 

내코드

 

처음에 생각한 방식은 다음과 같다.

1. 한변 길이가 4이상이면 나눠서 재귀로 돌기

2. 한변 길이가 2이면 r, c에 맞는 위치가 있는지 확인하고 없으면 다음 사분면 돌기

하지만 이렇게 하면 시간 초과가 났다.

# 잘못 푼 코드

# BaekJoon1074.py

def solv(n, x, y):
    global result
    if n == 2:
        if y == r and x == c:
            print(result)
            exit()
        elif y == r and x+1 == c:
            print(result + 1)
            exit()
        elif y+1 == r and x == c:
            print(result + 2)
            exit()
        elif y+1 == r and x+1 == c:
            print(result + 3)
            exit()
        else:
            result += 4
            return
    else:
        next_n = int(n/2)
        solv(next_n, x, y)
        solv(next_n, x + next_n, y)
        solv(next_n, x, y + next_n)
        solv(next_n, x + next_n, y + next_n)


result = 0
N, r, c = map(int, input().split())
solv(2 ** N, 0, 0)

 

그래서 검색을 통해 해결한 방식은 다음과 같다.

1. 해당 위치가 어느 사분면에 있는지 찾는다.

2. 사분면에 맞게 위치를 조정해주고 앞에 이동한 수 만큼 결과값에 더해준다.

3. 1-2를 반복하고 만약 4칸만 남게 되면 출력해준다.

# BaekJoon1074.py

N, r, c = map(int, input().split())
result = 0

while N > 1:
    size = (2 ** N) // 2
    if r < size and c < size:
        pass
    elif r < size and c >= size:
        result += size ** 2
        c -= size
    elif r >= size and c < size:
        result += size ** 2 * 2
        r -= size
    elif r >= size and c >= size:  # 4사분면
        result += size ** 2 * 3
        r -= size
        c -= size
    N -= 1

if r == 0 and c == 0:
    print(result)
if r == 0 and c == 1:
    print(result + 1)
if r == 1 and c == 0:
    print(result + 2)
if r == 1 and c == 1:
    print(result + 3)

아직 내가 잘 아는지는 모르겠어서 나중에 다시 풀어봐야겠다.

 

2022-7-19 다시품

N, r, c = map(int, input().split())


def recursion(start, end, n):
    global r, c

    length = end[0] - start[0]
    # 해당 사분면에 속한다면
    if end[0] >= r >= start[0] and end[1] >= c >= start[1]:
    	# 나눠진 사분면의 길이가 2가 아니라면
        if length - 1 > 0:
            recursion([start[0], start[1]], [(start[0] + end[0]) // 2, (start[1] + end[1]) // 2], n)
            recursion([start[0], (start[1] + end[1] + 1) // 2], [(start[0] + end[0]) // 2, end[1]], n + (((length + 1) // 2) ** 2))
            recursion([(start[0] + end[0] + 1) // 2, start[1]], [end[0], (start[1] + end[1]) // 2], n + ((length + 1) // 2) ** 2 * 2)
            recursion([(start[0] + end[0] + 1) // 2, (start[1] + end[1] + 1) // 2], [end[0], end[1]], n + (((length + 1) // 2) ** 2) * 3)
        # 나눠진 사분면의 길이가 2라면 4등분 된 경우이니 r, c 체크
        else:
            if [r, c] == start:
                print(n)
                return
            elif [r, c] == [start[0], start[1] + 1]:
                print(n + 1)
                return
            elif [r, c] == [start[0] + 1, start[1]]:
                print(n + 2)
                return
            else:
                print(n + 3)
                return


recursion([0, 0], [2 ** N - 1, 2 ** N - 1], 0)

 

 

참고

https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-1074-Z