백준 알고리즘 1074번 - Z [Python]

 

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

1074번: Z

solved.ac 에는 실버 1 난이도로 표기되어 있다.

나는 실버 2, 3도 빌빌대는데 다른 알고리즘(DP, DFS 등..)에 비해서 쉬운 것 같다

 

알고리즘 보다는 수식 찾는 문제라는 생각이 들어서

n, c, r이 주어졌을 때 값을 계산하는 방식으로 접근했다

---

 

위와 같이 표를 그려보니 규칙이 보이는 듯 했다.

 

[ r = 0  c = 8 ] 일때 값은 64이고

[ r = 8  c = 0 ] 일 때 값은 128이다.

 

 

0과 1을 비교하면, c가 1 증가하고 값은 1 증가했다

0과 4를 비교하면, c가 2 증가하고, 값은 4 증가했다

0과 16을 비교하면, c가 4 증가하고, 값은 16 증가했다

0과 64를 비교하면, c가 8 증가하고, 값은 64 증가했다

 

0과 2를 비교하면 r이 1 증가하고, 값은 2 증가했다

0과 8을 비교하면 r이 2 증가하고, 값은 8 증가했다

0과 32를 비교하면, r이 4 증가하고 값이 32 증가했다

0과 128을 비교하면, r이 8 증가하고 값이 128 증가했다

 

굳이 0이 아니더라도, r과 c중 하나를 고정시키고 값을 비교해보면 다 똑같은 규칙이 적용되는 것을 알 수 있었다.

 

 " 행이나 열이 2의 거듭제곱 만큼 이동할 때 규칙적으로 값이 증가하는 것 "을 찾았다.

 

 

c의 경우

2^0 이동 했을 때 → 4^0 증가

2^1 이동 했을 때 → 4^1 증가

2^2 이동 했을 때 → 4^2 증가

2^3 이동 했을 때 → 4^3 증가

 

r의 경우

2^0 이동 했을 때 → 2 x 4^0 증가

2^1 이동 했을 때 → 2 x 4^1 증가

2^2 이동 했을 때 → 2 x 4^2 증가

2^3 이동했을 때 → 2 x 4^3 증가

---

 

모든 자연수는 2의 거듭제곱의 합으로 표현할 수 있으며

위에서 찾은 규칙을 토대로, 0을 기준으로 삼아 r과 c의 값을 차근 차근 분해(?)하면 값을 알아낼 수 있다

 

예를 들어 테스트 케이스의 10, 511, 511의 경우

 

511 = 2^0 + 2^1 + 2^2 + ... + 2^8 이다.

 

r이 511 증가 했으므로, r의 증가분으로 인해 더해지는 값은

2 x ( 4^0 + 4^1 + 4^2 + ... + 4^8 )이며

 

c도 511 증가 했으므로, c의 증가분으로 인해 더해지는 값은

4^0 + 4^1 + 4^2 + ... + 4^8이다.

 

대충 계산기를 두들겨보면.. 262143이 나온다

 

규칙을 잘 추측한 것 같다

 

 

 

import sys

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

row = [2 * 4 ** i for i in range(n)]
column = [4 ** i for i in range(n)]

row.reverse()
column.reverse()

answer = 0
i = 0

while(r > 0):
    temp = 2 ** (n-i-1)
    if(r >= temp):
        r -= temp
        answer += row[i]
    i += 1

i = 0

while(c > 0):
    temp = 2 ** (n-i-1)
    if(c >= temp):
        c -= temp
        answer += column[i]
    i += 1

print(answer)

 

n, r, c를 입력받고 row와 column 리스트에 n의 값에 맞춰 값을 넣어준다

 

이후 reverse를 이용해서 순서를 뒤집었다

 

순서를 뒤집은 이유는 큰 값부터 차근 차근 빼려고..

 

그 이후 반복문을 이용해서 r과 c가 0이 될 때 까지 빼가면서

temp 변수에는 2의 거듭 제곱이 큰 순서대로 들어간다.

 

answer 변수에는 row 리스트와 column 리스트에 있는 값을 더해간다

 

설명이 참 부실하지만.. 그래도 최근 들어 혼자서 금방 푼 문제라서 기분이 좋다..