[백준] 1074번 : Z ☆

유형 : 재귀함수

[예제]

2 3 1

[출력]

11

---

1. 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 패키지 Online

 

** 핵심 아이디어
1. Z 모양을 구성하는 4가지 방향에 대하여 차례대로 재귀적으로 호출

 

def solve(n,x,y):
    global result
    if n == 2: # 2*2인 경우
    	if x == X and y == Y: # 아래 그림에서 1번
            print(result)
            return
        result += 1
     	
        if x == X and y + 1 == Y: # 아래 그림에서 2번
            print(result)
            return
        result += 1
        
        if x + 1 == X and y == Y: # 아래 그림에서 3번
            print(result)
            return
        result += 1
        
        if x + 1 == X and y + 1 == Y: # 아래 그림에서 4번
            print(result)
            return
    	result += 1
        return
 
    solve(n/2, x,y)
    solve(n/2, x,y+n/2)
    solve(n/2, x+n/2, y)
    solve(n/2, x+n/2, y+n/2)
 
 result = 0
 N, X, Y = map(int, input().split(' '))
 solve(2**N, 0, 0)

 

▷ 재귀를 이용하는게 핵심

    ▶ 4등분을 나눠서 하면 result 계산을 블록마다 해야해서 원하는 값을 얻지 못한다고 생각했다.

    ▶ 하지만 어차피 해당 좌표를 만날 때 result를 출력하고 return하기 때문에 문제가 없다!

▷ 4등분을 하여 각각 계산해야 한다는 생각까지는 했으나, 재귀로 구현을 못했다. 다시 해보자!!

 

 

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

1074번: Z