[Python] 백준 1074번 : Z

문제

1074번: Z

[ 문제 조건 ]

• Z 모양 순서대로 방문
• 입력한 r행 c열이 몇번 째로 방문하는지 출력

[ 해결순서 ]

• 1번째 풀이 -> 실패
  1. 재귀적으로 모든 분면의 모든 값을 확인해서
  2. 2X2 배열일 때 ( 더이상 등분하지 않아도 되면 )
  3. 조건에 맞을 때까지 값을 하나씩 늘려가면서 몇번째 방문인지 계산하다가
  4. r행 c열의 조건이면 여태껏 더한 방문값을 출력하고 종료한다.
  5. 이렇게 하면 시간 초과가 날 뿐만 아니라, 입력한 값에 포함하는 분면이 아닌 값들도 모두 확인해 비효율적인다.
• 2번째 풀이 (참고)
  1. 이 풀이는 아이디어를 참고한 후 코드를 짜면서 해석했는데, 이 문제를 풀 때 내가 처음에 생각해낸 아이디어와 비슷했다. (코드를 못 짜겠어서 1번째 풀이로 풀었지만..)
  2. 입력한 값이 몇 사분면인지 계산한 후, 예를 들어 3사분면에 속해있다면 1,2 사분면의 값들을 확인하지 않고 방문횟수만 더해줘도 방문처리가 된다.
  3. 그리고 시작점을 2^N X 2^N 배열의 중간값을 빼면 (12, 15, 18~19줄)
  4. n==1이 되었을 때(2 X 2 배열일 때) 시작점 0,0을 기준으로 입력한 값이 어디에 있는지 방문값을 맞게 더한다음에 출력하면 최종 값이 된다.

✏️한줄평

: 분할정복 문제를 저번에 풀었을 때도 1번풀이처럼 모든 경우의 수를 구한 다음에 값을 찾으면 그때 종료하고 출력하는 식으로 해결했는데, 비효율적인건 알고있었으나 시간초과가 날 수도 있는 문제가 있다는 것을 느꼈다. 그만큼 시간도 오래걸리고 메모리도 많이 차지할 테니 좀 더 효율적으로 코드를 짜는 방법을 공부해야겠다.

---

코드

1번째 풀이

	N, r, c = map(int,input().split())
	count = 0
	def zway(x ,y ,n):
	global count
	n = n // 2
	if n==1: #2X2 배열일 때
	if x==r and y==c: #예제 배열 기준으로 0
	print(count)
	return
	count+=1
	if x+1==r and y==c: #1
	print(count)
	return
	count+=1
	if x==r and y+1==c: #2
	print(count)
	return
	count+=1
	if x+1==r and y+1==c: #3
	print(count)
	return
	count+=1
	else:
	#탐색
	zway(x, y ,n) #1사분면
	zway(x, y+n, n) #2사분면
	zway(x+n, y, n) #3사분면
	zway(x+n, y+n, n) #4사분면
	zway(0,0,2 ** N)

view raw BOJ1074.py hosted with ❤ by GitHub

2번째 풀이

	n, y, x = map(int,input().split())
	count = 0
	while n>0:
	val = pow(2,n) // 2 # 2^n X 2^n 배열의 중간값
	#몇 사분면인지 알아내서 시작 값을 0,0으로 바꿔준다.
	if n > 1:
	# if r < val and c < val:
	# 그대로 1사분면이니까
	if y < val and x >=val: # 2사분면
	count += val**2 #1사분면 굳이 확인 안하고 값만 더함
	x -= val
	if y >= val and x < val: #3사분면
	count += (val**2) * 2
	y -=val
	if y >= val and x >=val: #4사분면
	count += (val**2) * 3
	x -= val
	y -= val
	if n == 1: #2 X 2 배열일 때
	if x==1 and y==0:
	count+=1
	elif x==0 and y==1:
	count+=2
	else:
	count+=3
	n-=1 #n을 줄이면서 범위를 줄임
	print(count)

view raw BOJ1074_2.py hosted with ❤ by GitHub