[파이썬] 백준 1074번 「Z」

문제

백준 1074번/실버1

https://www.acmicpc.net/problem/1074

1074번: Z

 

 

문제 해석

2의 몇 제곱인지 알려주는 n, 몇 번째 행인지 알려주는 r, 몇 번째 열인지 알려주는 c, 이렇게 3개를 입력받은 후, 행렬에서 해당 위치에 위치하는 수는 무엇인지 출력해야한다.

단 행렬에서 각 요소의 번호는 Z자를 그리면서 새겨지는 방식이다.

 

 

풀이 전략

N의 값이 최대 15이면 행의 길이는 2^15 = 32768, 열의 길이도 32768이다. 만약 최악의 경우 맨 마지막 위치까지 수를 계산해야한다고 가정을 하였다면 32738 * 32768 을 계산해야하는데 경우의 수가 약 10억이다. 실제 처음 행렬을 2차원 배열로 만들어서 z자를 그리며 계산하는 과정을 거쳤을 때 N = 10이었을 떄도 굉장히 오랜 시간이 걸렸었기에, 다른 방식으로 접근해야한다.

그럼 접근을 어떻게 해야할까?

한 가지 예시를 들어보겠다. 당신은 1~1000까지  수 중 마음에 드는 숫자 하나를 선택하면 내가 그 수를 11번의 질문으로 맞혀보는 상황이라고 가정하자. 그리고 당신은 77을 예상하였다.

 

• Q1. 당신이 생각한 수는 500보다 작나요?
• A : 네
• Q2. 당신이 생각한 수는 250보다 작나요?
• A: 네
• Q3. 당신이 생각한 수는 125보다 작나요?
• A: 네
• Q4. 당신이 생각한 수는 63보다 작나요?
• A : 아니요

벌써 4번밖에 질문을 하지 않았는데 범위는 63~125 사이로 줄었다. 처음 1~1000 범위라고 생각했을 때 4번만에 범위가 굉장히 줄었고, 이를 11번 반복할 때 값을 당신이 생각한 77의 수를 도출해낼 수 있다.

이 방식을 활용하여 이 Z문제를 해결할 수가 있다.

예제 1 을 테스트했을 떄, n=2, r=3, c=1이다.

먼저 행의 중앙값보다 r이 큰지 계산한다. 값이 크면 뒤쪽 절반 범위를 선택하고, r이 작다면 앞쪽 절반 범위를 선택한다.

 

그 후, 열의 범위를 계산한다. 열의 중앙값보다 c가 작으면 방금 계산한 범위의 절반의 앞쪽을 선택하고, 그렇지 않다면 뒤쪽 범위를 선택한다.

이를 1개의 값이 나올 때까지 반복한다. N의 값에 따라 계산횟수는 N번으로 크게 줄어들고, 이중포문을 사용하지 않아서 굉장히 빠르게 값을 구할 수 있다.

 

코드

import sys;

n, r, c = map(int, sys.stdin.readline().split());

k = 2**n -1; #행, 열의 사이즈
row_start = 0; #행 시작
col_start = 0; #열 시작

row_end = k; #행 끝
col_end = k; # 열 끝

row_center = (row_start + row_end)//2; #행의 중간 
col_center = (col_start + col_end)//2; #열의 중간 

num_min = 0; #번호 시작
num_max = 2**n * 2**n -1; #번호 끝 
num_center = (num_min + num_max)//2; #번호 중간

count = 0; #종료 조건을 위한 카운트


#계산 시작
while True:        
    if r<=row_center: #행 중간 지역보다 r 이 작으면
        row_end = row_center; #행 끝 부분을 행 중간부분으로 절반을 줄임
        num_max = num_center; #번호 최대 범위도 절반 줄임

    else:  #행 중간 지역보다 r이 크면
        row_start = row_center+1; #행 시작부분을 행중간 +1로 바꿈
        num_min = num_center+1; # #번호 시작부분도 중간 부분으로 옮겨줌

        
    row_center = (row_start + row_end)//2; #행 중앙 값 다시 계산
    num_center = (num_min + num_max)//2 #번호 중앙 값 다시 계산
    
    # print(f"{num_min} ~ {num_max}")
        
    
    # 행 계산 한 것 처럼 열 계산 똑같이 계산
    if c<=col_center:
        col_end = col_center;
        num_max = num_center;

    else:
        col_start = col_center+1;
        num_min = num_center+1;

    col_center = (col_start + col_end)//2;
    num_center = (num_min + num_max)//2
    
    # print(f"{num_min} ~ {num_max}")    
        
    
    #종료 조건, n만큼
    count+=1;
    if count >=n:
        break;
        
print(num_min); #값 출력

행 시작, 행 끝, 행 중간값

열 시작, 열 끝, 열 중간값,

숫자 시작, 숫자 끝, 숫자 중앙값 을 각각 계산하면서 범위를 줄여주기에 많은 변수가 사용되었고, 함수로 구현하는 것 보다는 반복문 한 번으로 끝내는 게 더 효율적이라고 생각하였다.

 

 

코드 실행

주석처리된 print문을 해제하고 결과를 확인해보자.

예제 1번을 토대로 아까 풀이전략에서 보인 것과 같게 나오는지 확인하면 처음 행의 중앙값대로 계산했을 때 8~15를 선택, 그 후 열의 중앙값대로 계산했을 때 8~11을 가져간 것 일치하였다.

 

 

결과

 

 

고찰

빠르게 풀고 시험공부하려고 문제 조건 보지않고 z자를 그리기 위해 재귀함수로 구현했었다. 함수로 구현하다보니 시작값 끝값이 2개씩 필요하였고, 재귀함수 4개로 각각 쪼개지는 상황을 만들다 보니 시간초과가 계속 일어나서 실패했었다가, 접근 방식을 바꿔서 겨우 해결하였다. 문제 조건이 굉장히 중요하다.

위와 같이 풀었을 때, 변수가 너무 많고 계속 값을 변경해 주어야해서 뇌로만 풀기에는 힘들었다.