BOJ_1074 Z

• TOC {:toc}

이 글은 백준 온라인 저지의 1074번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.06 (Python)

def Z(N, r, c):
    if N == 0:
        return 0
    unit = 2 ** (N - 1)
    return (unit ** 2) * ((r // unit) * 2 + c // unit) + Z(N - 1, r % unit, c % unit)


N, r, c = map(int, input().split())
print(Z(N, r, c))

아이디어 & 풀이

전체를 4분할 해서 어디에 있는지 파악한 뒤 4분할 한 그 조각을 다시 4분할 해서 위치를 파악하는 것을 반복한다.

• 입력 1을 예시로 들어보자. N = 2, r = 3, c = 1

우선 전체 칸을 다음과 같이 네 칸으로 나눌 수 있다.

• 한 칸의 단위는 2이며 실제로 4개의 블록으로 이루어져 있다.
• 표시가 되어있는 부분의 값들은 4 x 2 + 0 ~ 3 사이의 값을 갖게 된다.

이를 보다 일반적으로 해석해보자

• 현재 한 칸의 실제 단위는 2로 $2^{N-1}$이다.
• 4는 현재 한 덩어리의 크기로 $(2^{N-1})^2$ 이다.
• 2는 행과 열에 따라 0 ~ 3사이로 결정되는 값이며 $r \times 2 + c$로 계산할 수 있다.
  • $r$과 $c$가 현재 단위($2^{N-1}$)에서 각각 0, 1의 값을 가져야 위의 식이 성립하기 때문에
  • $r$과 $c$는 실제로 입력받은 r과 c를 $2^{N-1}$로 나눈 몫이다
    • r // (2 ** (N - 1)), c // (2 ** (N - 1))
• 0 ~ 3은 지금 표시된 지점만 다시 4등분을해서 위와 동일한 연산을했을 때 나오는 값으로 재귀 용법을 사용한다.

현재 표시된 지점만 다시 4분할 되도록 확대하면 다음과 같다.

• 실제 행은 2, 3행 이지만 이 부분만 보기 위해서는 다시 0, 1번째 행이 되어야 한다.
• 이 때 0, 1은 2, 3를 각각 한 칸의 단위인 2로 나눈 나머지임을 알 수 있다.
• 그러므로 재귀 함수로 넘기는 새로운 $r$과 $c$는 현재 r과 c를 $2^{N-1}$로 나눈 나머지이다
  • r // (2 ** (N - 1)), c // (2 ** (N - 1))

디버그

• 첫 행과 열이 1이 아닌 0부터 시작한다.
  • 그래서 예시로 주어진 3행 1열이 8번째가 아니고 11번째이다.

2022.03.20

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim();

const [N, r, c] = input.split(" ").map(Number);

function main(N, r, c) {
    if (N === 0) return 0;

    const unit = 2 ** (N - 1);
    const x = parseInt(c / unit);
    const y = parseInt(r / unit);
    const nc = parseInt(c % unit);
    const nr = parseInt(r % unit);

    return (x + 2 * y) * unit ** 2 + main(N - 1, nr, nc);
}

console.log(main(N, r, c));

참고 답안 1

# 풀이 1-1
N, r, c = map(int, input().split())
s = 0
while N:
    N -= 1
    s += (r >> N << 1 | c >> N) << N + N
    r &= (1 << N) - 1
    c &= (1 << N) - 1
print(s)

# 풀이 1-2
N, r, c = map(int, input().split())
print(int(bin(c)[2:], 4) + 2 * int(bin(r)[2:], 4))

아이디어 & 풀이

작성중

참고 답안 2

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

const [N, r, c] = input.split(" ").map(Number);

function main(N, r, c) {
    const unit = Math.pow(2, N - 1);
    const coord = (r >= unit) * 2 + (c >= unit);
    if (N <= 1) {
        return coord;
    }

    r = r >= unit ? r - unit : r;
    c = c >= unit ? c - unit : c;

    return unit * unit * coord + main(N - 1, r, c);
}

console.log(main(N, r, c));

아이디어 & 풀이

• 몫, 나머지를 사용하지 않고 반(unit)을 기준으로 값을 비교해서 위치를 정하고 계산했다.