[백준] 1074. Z

채연·2023년 1월 27일

baekjoon

목록 보기

8/26

문제

문제 설명

-> 문제는 간단하다.
-> 2의 몇 제곱할 것인지, 그리고 행, 열이 입력 값으로 들어온다.
-> 그럼 입력받은 행과 열에는 무슨 숫자가 있는지 찾으면 된다.

접근

1. 무작정 규칙을 찾아보았다.

제일 키 포인트였던 것은 이거였다.
이전 것에 4를 곱하면 원래 지금 내가 된다.
- 결국 당연한 얘기였다.
- 하지만, 여기에서 4가 아니라 3을 곱하면 어떻게 될까?

위의 그림은 n이 3일 때이다.
위에서 말했던 것처럼 나는 이전 것에 3을 곱해볼 것이다.
```
3 * (2^2 * 2^2) => 48
```
=> 결과로 4번째 블록의 첫 번째 값이 나왔다!

어? 이렇게해서 값을 구할 수 있다면, 이런식으로 접근을 해보자

블록들을 다 2*2 블록으로 만든다.
-> 2*2 블록으로 만든 이유는 2*2 블록에서의 첫 번째 값을 구하기만 한다면 나머지 값들 구하는 것은 완전 쉬웠기 때문이다.
-> 예를 들어, 48, 49, 50, 51 의 2*2 블록이 있다면, 48의 값을 찾고 각각 +1, +2, +3을 더해주면 된다.
식 세우기
```
2^(n+1) * (2 * 2)
```
-> 2 * 2의 코드 블록이 2의 n-1제곱만큼 있어야 한다.
블록 생각해보기

5행과 5열에 있는 값을 구해보고자 한다.
일단 그림으로 그렸을 때 5행 5열은 51이다.
블록을 2개로 쪼개었으니까 이 5행 5열을 2로 나누게 되면 2블록 / 2블록이 나오게 되고, 5행 5열은 그다음 3블록 3번째라는 정보가 나오게 된다!
-> 여기서 이제 행이 짝수일 경우, 행이 홀수일 경우 등을 고려하여 각각 +1, +2, +3을 구해주면 답이 나오게 된다.

=> 하지만, 계속 짜다보니 이 방법은 너무 더러운 방법 같았다..!
=> 블록을 2개로 짜르는 것보단, 사분면을 이용해서 풀 수 있을 것 같기에 사분면으로 도전!

2. 사분면 이용

이것도 마찬가지로 저 위에 있는 식을 이용한다.

* 여기에서는 편의를 위해 1사분면이 왼쪽 위, 2사분면이 오른쪽 위, 3사분면이 왼쪽 아래, 4사분면이 오른쪽 아래라고 정의

수도코드

1사분면일 때는 위의 식에서 4라고 되어 있는 부분을 0, 2사분면은 1, 3사분면은 2, 4사분면은 3로 놓는다.
-> 이렇게 한다면, 우리는 각 사분면의 첫 번째 값을 알 수 있다.
각 사분면의 첫째 값을 결과 값에 더한 후, 다시 진행을 해나간다.
-> 진행이 될 때마다 차원의 값(n)은 하나씩 줄여준다.
-> 2사분면일 때는 열을 2의 n-1 승만큼 지우고, 3사분면일 때는 행을 2의 n-1승만큼, 4사분면일 때는 행과 열을 둘다 2의 n-1승만큼 지운다.

수도코드 기반한 예시
-> n이 3일 때, 5행 5열인 51을 찾아본다.

사분면 구하기
5행은 2의 n-1승보다 크고, 5열도 2의 n-1승보다 크기 때문에 4사분면이다.

따라서 위의 식에서 3를 곱해준다 => 3 * 2^2 * 2^2 = 48
값 정리
-> 48을 킵해두고, 행 / 열을 2의 n-1승(4)만큼씩 지운다.
-> 행은 1, 열은 1
-> n은 -1 해줌
또 사분면 구하기
1행은 2의 n-1승(2)보다 작거나 같고, 1열도 2의 n-1승(2)보다 작거나 같다-> 1사분면

따라서 위의 식에서 0을 곱해준다.
또 값 정리
-> 킵해둔 48에다가 0을 더하고, 1사분면이니 행, 열은 가만히 놔둠
-> 행은 1, 열은 1
-> n은 -1 해줌
또 사분면 구하기
1행은 2의 n-1 승(0)보다 크고, 1열도 크다 -> 4사분면

따라서 위의 식에 3을 곱해준다.
또 값 정리
-> 킵해둔 48에다가 3을 더함 / 4사분면이니 행, 열에다가 -1 해줌
-> 행은 0, 열은 0
-> n은 -1 해줌 => n이 0됨
n이 0이니까 끝
킵해둔 거 출력 => 51

코드

N, r, c = map(int, input().split())
result = 0
while(N != 0):
    if((r < (2**(N-1)) and ( c < (2**(N-1))))): # 만약, 1사분면이라면
        result += 0 * (2**(N-1)) * (2**(N-1))

    elif((r < (2**(N-1)) and (c >= (2**(N-1))))): # 2사분면
        result += 1 * (2**(N-1)) * (2**(N-1))
        c -= 2**(N-1)

    elif((r >= (2**(N-1)) and (c < (2**(N-1))))): # 3사분면
        result += 2 * (2**(N-1)) * (2**(N-1))
        r -= 2**(N-1)

    else:   # 4사분면
        result += 3 * (2**(N-1)) * (2**(N-1))
        r -= 2**(N-1)
        c -= 2**(N-1)

    N -= 1

print(result)

-> 코드는 수도코드 그대로다!