-
백준(BOJ) 15562 톱니바퀴(2)알고리즘 풀이/백준(Boj) 2019. 10. 10. 13:22
문제 : https://www.acmicpc.net/problem/15662
15662번: 톱니바퀴 (2)
총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다. 아래 그림은 T가 4인 경우이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다
www.acmicpc.net
풀이 :
한번 돌릴때의 일어나는 모든 상호작용은 큐로 처리한다. 즉 어떤 한 시계의 방향을 돌렸을때의 양옆의 톱니바퀴가 돌려질 수 있고 그로인해 또 양옆에 톱니바퀴가 돌려질 수 있기 때문이다.
처음 상태에 톱니들이 어떤 극으로 맞닿아 있는지 beforeRotate 에 넣어준다.
큐에 넣을 조건으로 그 톱니바퀴를 돌린 적이 없어야 하고 beforeRotate의 값이 달라야 넣을 수 있다.
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 9944번 NxM 보드 완주하기 (0) 2019.10.13 백준(BOJ) 12996번 Acka (31) 2019.10.13 백준(BOJ) 2234번 성곽 (0) 2019.10.05 백준(BOJ) 1600번 말이 되고픈 원숭이 (63) 2019.10.03 백준(BOJ) 14442번 벽 부수고 이동하기 2 (31) 2019.10.01