백준 14891 톱니바퀴 코드, 해설(파이썬)/ 삼성기출, 실버1 구현문제

코드만 궁금한 분은 깃허브 링크 눌러주세요

GitHub - Rhyankwon/algorithms

 

문제 설명 ㄱㄱ~~ 오랜만에 문제 푼거 올리려니까 내가 그동안 어떤 식으로 글 썼었는지 까먹음;;

 

 

4개의 톱니바퀴가 있고 톱니바퀴를 움직인다.

 

톱니바퀴는 1번부터 4번까지 있고, 주어진 입력에 따라 각각을 시계방향 또는 반시계방향으로 회전시킨다.

 

이 때 각 톱니바퀴의 끝에는 주어지는 입력에 따라 N극 S극이 정해져잇는데, 이 극성끼리의 관계에 따라 옆쪽 톱니에도 영향을 준다. 만약 다른 쪽 톱니바퀴와 마주치는 쪽이 서로 각각 N극과 S극 이면 영향을 줘서 움직이고 그렇지 않으면 안 움직인다. 따라서 만약 톱니바퀴1번이 시계방향으로 회전하는데 여기와 붙어있는 톱니바퀴2번..의 극성이 톱니1과 반대이면 톱니바퀴2번은 반시계로 회전하게 된다.

 

 

*****풀이 논리*****

 

1. 톱니바퀴와 회전 방향이 주어지면 우선 현재 톱니바퀴를 회전한다.

 

2. 해당 톱니바퀴의 오른쪽과 왼쪽에 있는 톱니바퀴들을 각각 탐색하는데..

 

3. 단방향으로 설명하면, 현재 톱니바퀴가 1(시계방향) 방향으로 회전하면 그 오른쪽이나 왼쪽 톱니는 -1(반시계방향)방향으로 회전해야한다.

 

4. 따라서 방향을 설정한 뒤, 옆쪽 방향은 연쇄적으로 매번 * -1이 되도록 해서 방향을 바꿔준다.

 

5. 이 때 만일 옆쪽 톱니바퀴와 서로 같은 극인 경우( 1/1 혹은 0/0) 해당 톱니는 회전하지 않고 이 이후의 톱니바퀴들도 계속 회전하지 않는다. 입력에 따라 계속해서 1~5를 반복하면 끝.

 

나 같은 경우에는 위5번을 구현할 때, 방향을 1은 시계 -1은 반시계 0은 정지로 해서 풀었다. 이렇게 하면 방향에 -1을 곱해서 계속해서 방향을 바꿔주면서도 한번 톱니바퀴가 멈추면 그 이후에는 계속해서 톱니바퀴를 멈출 수 있다.

 

나는 각 행을 회전시키는 함수와 모든 톱니바퀴를 움직이는 함수 이렇게 두개를 만들어서 풀었고, 내가 생각했을 때 가장 중요한 부분은 5번이다.

 

    tmp_d = d
    for t_ in range(t+1, 4): #오른쪽으로 탐색
        if tmp_d != 0 and topni_arr[t_][RIGHT] != topni_arr[t_-1][LEFT]:
            tmp_d *= -1 #지난 톱니바퀴 방향과 반대로 움직인다.
            tmp_arr[t_] = rot(t_, tmp_d)
        else :
            tmp_arr[t_] = topni_arr[t_]
            tmp_d = 0 #만약 한번 안 움직이면 연쇄적으로 계속 안움직인다. tmp_d==0이면 단순 복사.

tmp_d가 반시계 혹은 시계의 그 방향이다.

 

 

풀어보면 괜찮은 문제. 좀 복잡하지만 머리를 잘 붙들고 생각하면 풀만하다. 나는 효율성 문제는 정말..못풀겠어서 차라리 이런 구현문제가 나은것같다. 푸는데 40~50분정도 걸린 것 같다. 이정도면 괜찮지뭐.... 실버1이라서 근데.. 삼성기출에 골드가 많아서 사실 ㅠ 다시 코딩테스트 연습 시작했으니까 열심히 해야겠다.