1074번 Z

골드 V

💡문제 분석 요약

분할 정복

💡알고리즘 설계

전체 탐색을 하려면 연산이 많아지므로 분할 탐색 알고리즘을 사용해야한다.

이때, 모든 부분을 분할해서 탐색하면 안된다. (시간 복잡도 개선이 없기에)

DP와 반대로 Top-Down 방식이기에 전체→작은 부분으로 내려간다.

일단 4부분으로 자르고 그 자른 범위에 r,c가 있다면 탐색을 진행한다.

만약 n이 2인경우 배열은 4*4이고, 4조각으로 자르면, 한 변의 길이는 2이다.

X>r , X+N≤R , y>c, y+n ≤c중 하나라도 해당되면 cnt+=n**2를 더해주고 끝낸다.

위의 조건은 구하려는 r과 c가 범위 내에 없다는 뜻이다. 그러니 분할 정복으로 더 계산하지 않고, 넘어간 숫자 만큼을 cnt에 더해준다.

n//=2로 잘라주고, (0,0) (0,2) (2,0) (2,2)처럼 자른 범위를 하나씩 돌며 수행한다.

만약 n이 2로 내려오면 변의 길이가 2가 되므로 z를 가진 사각형이 된다.

💡코드


import sys

def dc(x,y,n):
    global cnt
    if x>r or x+n <= r or y>c or y+n <= c:
        cnt += n**2
        return 
    
    if n > 2:
        n//=2
        dc(x,y,n)
        dc(x,y+n,n)
        dc(x+n,y,n)
        dc(x+n,y+n,n)
    else:
        if x==r and y==c:
            print(cnt)
        elif x==r and y+1==c:
            print(cnt+1)
        elif x+1==r and y==c:
            print(cnt+2)
        else:
            print(cnt+3)
        sys.exit()
        
n,r,c = map(int,input().split())
cnt = 0
dc(0,0,2**n)
'''
이 외에 다른 코드
'''
import sys
input= sys.stdin.readline
N,r,c = map(int,input().strip().split())

def z(n, r, c, res):
    length = 2 ** n  # 배열 길이
    half = length // 2  # 사분면으로 만들기위한 배열길이의 절반길이 구하기
    if n == 1: # 재귀 종료조건 2x2 4 최소 사분면이 만들어질 경우
        print(2 * r + c + res)  # row가 늘어나면 도착횟수가 2씩 늘어나고 colunm이 늘어나면 1씩 늘어난다.
        return

    if r >= half and c >= half:  # 4사분면일떄 조건
        z(n - 1, r - half, c - half, res + 3 * half * half)
    elif r >= half > c:  # 3사분면일때 조건
        z(n - 1, r - half, c, res + 2 * half * half)
    elif r < half <= c:  # 2사분면일때 조건
        z(n - 1, r, c - half, res + half * half)
    else:  # 1사분면일때 조건
        z(n - 1, r, c, res)
        
        
z(N, r, c, 0)

💡틀린 이유

  • 순차적으로 숫자가 더해져서 모든 것을 탐색해 봐야 한다고 생각한게 가장 컸다. 즉, 분할 탐색 시 넘어가는 조건을 어떻게 설정하지? 도 막막했다.
    • 그저 4분면 중 어느 사분면인지 차례로 보고 넘어가기 때문에 가능한 조건이다. 예를 들어, 3 사분면에 있으면 1,2를 지나칠 때 숫자를 지나친 만큼 더해주면 된다. 그리고 3 사분면 안에서도 차례대로 쪼개서 더하기 때문에 이전 숫자들을 그대로 더하면 값이 나온다.
  • 분할 정복 알고리즘 문제를 잘 안 풀어봐서 감은 오는데 구현이 어렵다. 재귀로 제일 작은 곳 까지 가서, 풀고 가는건 이해하는데 구현을 어떻게 해야하지? 계속 막힌다.
  • 지금 까지의 분할정복은, 최소 4분면으로 쪼개는 조건이 이미 문제에 제시되어있다. 따라서 4개로 쪼개는 것을 활용해야 하며, 종료 조건은 더 이상 쪼갤 수 없을 때이다.
  • 코드가 계속 쪼개는 코드와 쪼개지 않는 코드로 나뉘어져 있다. 여기서 분할 정복 후 모든 코드를 탐색하지 않는 조건을 맨 위의 if 문으로 걸러 return해줘 더이상 분할 하지 않도록 했다.
  • 만약, 쪼갤 때 까지 쪼개고 ( 함수 재귀 호출) 4개 중에 하나라면, 순서대로 (z모양 순으로) print할 값을 계산하여 출력한다.

💡 기억할 것

  • divide conquer에 대해 좀 더 알자. 큰 문제를 작은 문제로 쪼개고, 쪼갠 것을 다시 더하면서 값을 계산하는 방식. 분할 정복은 dp와 달리 쪼갠 것이 독립적이다.
    1. 분할: 문제를 작은 하위 문제로 분할.
    2. 정복: 각 하위 문제는 재귀적으로 해결.
    3. 결합: 하위 문제의 해결책을 결합하여 원래 문제를 해결.