[Baekjoon] - 1074. Z(S1)
1. Problem 📃
📚 출처 - 1074 - Z
문제 설명
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
제한
- 1 ≤ N ≤ 15
- 0 ≤ r, c < 2N
0
입출력 예
예제 입력 | 예제 출력 |
---|---|
2 3 1 | 11 |
3 7 7 | 63 |
1 0 0 | 0 |
4 7 7 | 63 |
10 511 511 | 262143 |
10 512 512 | 786432 |
2. Logic 👨🏫
예를 들어, N=3, r=7, c=7를 입력 받았다고 가정한다면 답으로 도출되어야 하는 값은 63이다. 이 과정을 한번 살펴봐보자.
먼저 이렇게 4개의 영역으로 분할했을 때 규칙을 살펴보면
처음 (7, 7)은 N=3인 영역에서 제4사분면에 해당됩니다.
(가로 좌표 7 >= 2의 2승, 세로 좌표 7 >= 2의 2승이므로 제4사분면)
- 제1사분면은 0부터 시작
- 제2사분면은 16
- 제3사분면은 32
- 제4사분면은 48부터 시작
두 번째로 쪼갰을때는 (7, 7)의 좌표는 (3, 3)이 됩니다.
(가로 세로가 각각 네칸씩 줄어드니깐, 7 - 2의 2승 = 3)
또한 (3, 3)은 N = 2인 영역에서 제4사분면에 해당됩니다.
(3 >= 2의 1승, 3 >= 2의 1승이므로 제 4사분면)
48을 뺐다고 가정한다면, 제4 사분면은 12부터 시작합니다.
세 번째로 쪼개면 (3, 3)의 좌표는 (1, 1)로, 제 4사분면에 해당합니다.
(가로 세로 두 칸씩 줄어드니깐, 3 - 2의1승 = 1)
제 4사분면인 (1, 1)은 3입니다.
그래서 48 + 12 + 3은 63입니다.
3. Code 💻
1. 참고해서 이해해 푼 코드 😁
N, r, c = map(int, input().split())
ans = 0
while N != 0:
N -= 1
size = 2 ** N
if r < size and c < size: # 1사분면
ans += (size) * (size) * 0
elif r < size and c >= size: # 2사분면
ans += (size) * (size) * 1
c -= size
elif r >= size and c < size: # 3사분면
ans += (size) * (size) * 2
r -= size
else: # 4사분면
ans += (size) * (size) * 3
c -= size
r -= size
print(ans)
Author And Source
이 문제에 관하여([Baekjoon] - 1074. Z(S1)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@odh0112/Baekjoon-1074.-ZS1
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
N, r, c = map(int, input().split())
ans = 0
while N != 0:
N -= 1
size = 2 ** N
if r < size and c < size: # 1사분면
ans += (size) * (size) * 0
elif r < size and c >= size: # 2사분면
ans += (size) * (size) * 1
c -= size
elif r >= size and c < size: # 3사분면
ans += (size) * (size) * 2
r -= size
else: # 4사분면
ans += (size) * (size) * 3
c -= size
r -= size
print(ans)
Author And Source
이 문제에 관하여([Baekjoon] - 1074. Z(S1)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@odh0112/Baekjoon-1074.-ZS1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)