Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- level0
- 그리디
- level2
- 프로그래머스
- 수학
- 브루트포스
- 운영체제
- 가상메모리
- DP
- 스택
- dfs
- BFS
- level3
- level1
- 가상메모리 관리
- dict
- 딕셔너리
- 힙
- 재귀
- 백준
- BOJ
- 파이썬
- python
- programmers
- 코딩테스트
- 다이나믹 프로그래밍
- MYSQL
- 다익스트라
- N과M
- 구현
Archives
- Today
- Total
동캄의 코딩도장
백준 1074 [Z] 파이썬 본문
https://www.acmicpc.net/problem/1074
# 백준 1074 Z
N,r,c,=map(int,input().split())
answer=0
def search(r,c,N,tr,tc): # 왼쪽부터 현재 행, 현재 열, 승수, 목표 행, 목표 열
global answer
if r==tr and c==tc: #현재 행,열이 목표 행,열이면 함수종료
return
half_distance=2**(N-1) #정사각형의 한 변의 절반 길이
quarter_area=half_distance*half_distance #정사각형 넓이의 4분의 1
criteria_r,criteria_c=r+half_distance,c+half_distance #4등분했을 때, 구간을 나누는 기준
if tr<criteria_r:
if tc<criteria_c: #왼쪽 위 구간에 있다면
search(r,c,N-1,tr,tc)
else: #오른쪽 위 구간에 있다면
answer+=quarter_area
search(r,c+half_distance,N-1,tr,tc)
else:
if tc<criteria_c: #왼쪽 아래 구간에 있다면
answer+=quarter_area*2
search(r+half_distance,c,N-1,tr,tc)
else:
answer+=quarter_area*3 #오른쪽 아래 구간에 있다면
search(r+half_distance,c+half_distance,N-1,tr,tc)
search(0,0,N,r,c) #탐색 시작
print(answer)
분할 정복을 이용해서 해결하는 문제다.
z를 따라 방문한다는 것은 왼쪽위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 방문한다는 것을 의미한다.
따라서 4분할 한 뒤, 목표하는 점의 행, 열의 위치가 4분할 영역 중 어느 영역에 속하는지 파악한다.
그리고 다시 그 영역을 4분할하는 것을 재귀적으로 반복하여 목표점을 찾아낸다.
'코테 > BOJ' 카테고리의 다른 글
백준 1052 [물병] 파이썬 (0) | 2024.01.16 |
---|---|
백준 11286 [절댓값 힙] 파이썬 (0) | 2023.03.21 |
백준 11403 [경로 찾기] 파이썬 (0) | 2023.03.21 |
백준 5525 [IOIOI] 파이썬 (0) | 2023.03.21 |
백준 1992 [쿼드트리] 파이썬 (0) | 2023.03.21 |