๋ฌธ์
https://www.acmicpc.net/problem/14891
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x0D๊ฐ - ์๋ฎฌ๋ ์ด์
์๊ณ ๋ฆฌ์ฆ: ์๋ฎฌ๋ ์ด์
ํ์ด
์ด 8๊ฐ์ ํฑ๋๋ฅผ ๊ฐ์ง๊ณ ์๋ ํฑ๋๋ฐํด 4๊ฐ๊ฐ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ผ๋ ฌ๋ก ๋์ฌ์ ธ ์๋ค. ๋, ํฑ๋๋ N๊ทน ๋๋ S๊ทน ์ค ํ๋๋ฅผ ๋ํ๋ด๊ณ ์๋ค. ํฑ๋๋ฐํด์๋ ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๋๋ฐ, ๊ฐ์ฅ ์ผ์ชฝ ํฑ๋๋ฐํด๊ฐ 1๋ฒ, ๊ทธ ์ค๋ฅธ์ชฝ์ 2๋ฒ, ๊ทธ ์ค๋ฅธ์ชฝ์ 3๋ฒ, ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ํฑ๋๋ฐํด๋ 4๋ฒ์ด๋ค.
์ด๋, ํฑ๋๋ฐํด๋ฅผ ์ด K๋ฒ ํ์ ์ํค๋ ค๊ณ ํ๋ค. ํฑ๋๋ฐํด์ ํ์ ์ ํ ์นธ์ ๊ธฐ์ค์ผ๋ก ํ๋ค. ํ์ ์ ์๊ณ ๋ฐฉํฅ๊ณผ ๋ฐ์๊ณ ๋ฐฉํฅ์ด ์๊ณ , ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ํ์ ํ๋ค.
ํฑ๋๋ฐํด๋ฅผ ํ์ ์ํค๋ ค๋ฉด, ํ์ ์ํฌ ํฑ๋๋ฐํด์ ํ์ ์ํฌ ๋ฐฉํฅ์ ๊ฒฐ์ ํด์ผ ํ๋ค. ํฑ๋๋ฐํด๊ฐ ํ์ ํ ๋, ์๋ก ๋ง๋ฟ์ ๊ทน์ ๋ฐ๋ผ์ ์์ ์๋ ํฑ๋๋ฐํด๋ฅผ ํ์ ์ํฌ ์๋ ์๊ณ , ํ์ ์ํค์ง ์์ ์๋ ์๋ค. ํฑ๋๋ฐํด A๋ฅผ ํ์ ํ ๋, ๊ทธ ์์ ์๋ ํฑ๋๋ฐํด B์ ์๋ก ๋ง๋ฟ์ ํฑ๋์ ๊ทน์ด ๋ค๋ฅด๋ค๋ฉด, B๋ A๊ฐ ํ์ ํ ๋ฐฉํฅ๊ณผ ๋ฐ๋๋ฐฉํฅ์ผ๋ก ํ์ ํ๊ฒ ๋๋ค.
ํฑ๋๋ฐํด์ ์ด๊ธฐ ์ํ์ ํฑ๋๋ฐํด๋ฅผ ํ์ ์ํจ ๋ฐฉ๋ฒ์ด ์ฃผ์ด์ก์ ๋, ์ต์ข ํฑ๋๋ฐํด์ ์ํ๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
(์๊ธ์ ๊ทธ๋ฆผ๊ณผ ํจ๊ป ๋ณด๋๊ฒ ์ดํดํ๊ธฐ ์ฝ๋ค.)
ํฑ๋๋ฐํด์ ์ ๋ณด๋ 12์ ๋ฐฉํฅ์ผ๋ก๋ถํฐ 8๊ฐ ์ฃผ์ด์ง๋ค.
์๊ณ๋ฐฉํฅ์ผ๋ก ๋ถ, ๋ถ๋, ๋, ๋จ๋, ๋จ... ์์ด๊ณ ์ธ๋ฑ์ค๋ก ๋ฐ์ง๋ฉด 0๋ถํฐ 7๊น์ง๊ฐ ๋๊ฒ ๋ค.
๊ฐ ํฑ๋๋ฐํด๊ฐ ์ ํฑ๋๋ฐํด์ ๋ง๋ฟ๋ ๋ถ๋ถ์ ์/๋ ๋ถ๋ถ, ์ธ๋ฑ์ค๋ก๋ [-2], [2]๋ฒ์งธ ์์ ๋ถ๋ถ์ด๋ค.
๋๋ ์ฌ๊ท๋ก ํ์๋ค.
ํจ์ rotate()์ 'ํ์ ํ ๋ฐฉํฅ, ํ์ ์ํฌ ํฑ๋๋ฐํด์ ๋ฒํธ, ์ด๋ฏธ ํ์ ํ ํฑ๋๋ฐํด๋ฅผ ์ ์ฅํ set()'๋ฅผ ๋๊ฒจ์ค๋ค.
์ฐ์ ํ์ฌ ํฑ๋๋ฐํด์ [-2], [2]๋ฅผ ์ ์ฅํด๋๋ค. ๊ฐ๊ฐ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ๊ณผ ๋ง๋ฟ๋ ๋ถ๋ถ์ด๋ค.
๊ทธ ํ ํฑ๋๋ฐํด๋ฅผ ๋ฐฉํฅ์ ๋ง๊ฒ ํ์ ์ํค๊ณ , ์ด๋ฏธ ํ์ ํ ํฑ๋๋ฐํด์ ์ถ๊ฐํ๋ค.
๊ทธ๋ฆฌ๊ณ 1) ์ ์ ํฑ๋๋ฐํด๊ฐ 1~4 ๋ฒ์ ๋ด์ ์๋์ง, 2) ์ด๋ฏธ ํ์ ํ ํฑ๋๋ฐํด ๋ฆฌ์คํธ์ ์กด์ฌํ๋์ง, 3) ์์์ ๋ฏธ๋ฆฌ ๊ตฌํด๋ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ๊ฐ๊ณผ ๋์ผํ์ง ์๋์ง ์ฒดํฌํ๋ค.
๋ง์ฝ ์ ์กฐ๊ฑด์ ๋ชจ๋ ํด๋น๋๋ค๋ฉด ์ฌ๊ท๋ฅผ ์คํํ๊ณ ์๋๋ฉด pass.
๋ชจ๋ ํ์ ์ ๋ง์น ํ ํฑ๋๋ฐํด์ 12์ ๋ฐฉํฅ, ์ฆ [0]๋ฒ ์ธ๋ฑ์ค๊ฐ๋ค์ ์ฒดํฌํ๋ค.
N์ด๋ผ๋ฉด 0, S๋ผ๋ฉด 2^ํฑ๋๋ฐํด์ ๋ฒํธ ๊ฐ์ผ๋ก ๋ณํํ๋ฉด ๋๋ค.
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 31120KB / ์๊ฐ: 36ms
from sys import stdin
input = stdin.readline
gears = [list(map(int, input().rstrip())) for _ in range(4)]
K = int(input())
rotation = [list(map(int, input().split())) for _ in range(K)]
# ๊ฐ ํฑ๋๋ฐํด๊ฐ ๋ง๋ฟ๋ ๋ถ์๋ [2], [-2]๋ฒ ํฑ๋.
def rotate(direction, gear, rotated):
left, right = gears[gear][-2], gears[gear][2]
if direction == 1:
gears[gear] = gears[gear][-1:] + gears[gear][:-1]
else:
gears[gear] = gears[gear][1:] + gears[gear][:1]
rotated.add(gear)
if gear-1 >= 0 and gear-1 not in rotated and gears[gear-1][2] != left:
rotate(-direction, gear-1, rotated)
if gear+1 <= 3 and gear+1 not in rotated and gears[gear+1][-2] != right:
rotate(-direction, gear+1, rotated)
for idx, direction in rotation:
rotate(direction, idx-1, set())
# N๊ทน์ 0, S๊ทน์ 1
ret = [0 if gears[i][0] == 0 else 2**i for i in range(4)]
print(sum(ret))
๋จธ๋ฆฌ๋ฅผ ์์จ๋ ๋๋ ๋ฌธ์ ๋ผ ํ๋ณตํ๋ค...