ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 14891.톱니바퀴
    알고리즘/백준 BAEK JOON 2020. 5. 1. 19:31

    이번에 풀어볼 문제는 백준의 14891 톱니바꾸다.

    난이도가 그렇게 어렵지는 않다. 쪼끔 까다롭게 느껴질뿐..

    모든 문제가 그렇듯 이 문제 역시 초반에 구상을 잘하고 들어가야한다.

    그렇지 않으면 자신이 굉장히 까다롭게 느껴질 것이고 생각보다 많은 시간이 소요될 수 있다. 

    ( 나의 코드를 추천하지는 않는다.. 너무 하수의 풀이인 것 같기 때문에...ㅎㅎ)

     

    14891번: 톱니바퀴

    총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려

    www.acmicpc.net

     

     

    우선 나의 경우는 이 문제를 조립식으로 생각했다.

    1. 톱니바퀴의 시계방향, 반시계방향 함수를 구현

    2. 톱니바퀴 사이의 N극, S극에 따라 돌지 말지를 판단하는 함수

    3. 톱니바퀴는 연쇄적인 동작과정을 가지고 있기 때문에 이것이 연쇄적인지를 체크 (이 부분을 빼먹어서 조금 헤맸다)

    -> 예를 들어 1번을 돌리기로 했는데 2번이 안돌면 당연히 3번도 안돌아야한다.

     

    난이도는 생각보다 어렵지 않으니 그냥 순서대로 천천히 생각하고 예외만 생각해주면 풀 수 있다.

     

     

     

    < Code 설명 >

    #pragma warning(disable:4996)
    #include <iostream>
    #include <deque>
    
    using namespace std;
    
    void make_top(deque<int>& a){
    	int tmp;
    	for (int i = 0; i < 8; i++){
    		scanf("%1d",&tmp);
    		a.push_back(tmp);
    	}
    }
    void si(deque<int>& a){
    	a.push_front(a.back());
    	a.pop_back();
    }
    void ban(deque<int>& a){
    	a.push_back(a.front());
    	a.pop_front();
    }
    
    void check(deque<int>&a, deque<int>&b, deque<int>&c, deque<int>&d, int t, int chg){		
    	bool check[3] = { false, };
    	if (t == 1 && chg == 1){
    		if (a[2] != b[6])
    			check[0] = true;
    		if (b[2] != c[6] && check[0]==true)
    			check[1] = true;
    		if (c[2] != d[6] && check[1]==true)
    			check[2] = true;
    		
    		si(a);
    		if (check[0] == true)
    			ban(b);
    		if (check[1] == true)
    			si(c);
    		if (check[2] == true)
    			ban(d);
    	}
    	else if (t == 1 && chg == -1){
    		if (a[2] != b[6])
    			check[0] = true;
    		if (b[2] != c[6] && check[0] == true)
    			check[1] = true;
    		if (c[2] != d[6] && check[1] == true)
    			check[2] = true;
    
    		ban(a);
    		if (check[0] == true)
    			si(b);
    		if (check[1] == true)
    			ban(c);
    		if (check[2] == true)
    			si(d);
    	}
    	else if (t == 2 && chg == 1){
    		if (a[2] != b[6])
    			check[0] = true;
    		if (b[2] != c[6])
    			check[1] = true;
    		if (c[2] != d[6] && check[1]==true)
    			check[2] = true;
    
    		si(b);
    		if (check[0] == true)
    			ban(a);
    		if (check[1] == true)
    			ban(c);
    		if (check[2] == true)
    			si(d);
    	}
    	else if (t == 2 && chg == -1){
    		if (a[2] != b[6])
    			check[0] = true;
    		if (b[2] != c[6])
    			check[1] = true;
    		if (c[2] != d[6] && check[1] == true)
    			check[2] = true;
    
    		ban(b);
    		if (check[0] == true)
    			si(a);
    		if (check[1] == true)
    			si(c);
    		if (check[2] == true)
    			ban(d);
    	}
    	else if (t == 3 && chg == 1){
    		if (b[2] != c[6])
    			check[1] = true;
    		if (c[2] != d[6])
    			check[2] = true;
    		if (a[2] != b[6] && check[1]==true) 
    			check[0] = true;
    
    		si(c);
    		if (check[0] == true)
    			si(a);
    		if (check[1] == true)
    			ban(b);
    		if (check[2] == true)
    			ban(d);
    	}
    	else if (t == 3 && chg == -1){
    		if (b[2] != c[6])
    			check[1] = true;
    		if (c[2] != d[6])
    			check[2] = true;
    		if (a[2] != b[6] && check[1] == true)
    			check[0] = true;
    
    		ban(c);
    		if (check[0] == true)
    			ban(a);
    		if (check[1] == true)
    			si(b);
    		if (check[2] == true)
    			si(d);
    	}
    	else if (t == 4 && chg == 1){
    		if (c[2] != d[6])
    			check[2] = true;
    		if (b[2] != c[6] && check[2]==true)
    			check[1] = true;
    		if (a[2] != b[6] && check[1]==true)
    			check[0] = true;
    
    		si(d);
    		if (check[0] == true)
    			ban(a);
    		if (check[1] == true)
    			si(b);
    		if (check[2] == true)
    			ban(c);
    	}
    	else if (t == 4 && chg == -1){
    		if (c[2] != d[6])
    			check[2] = true;
    		if (b[2] != c[6] && check[2] == true)
    			check[1] = true;
    		if (a[2] != b[6] && check[1] == true)
    			check[0] = true;
    		ban(d);
    		if (check[0] == true)
    			si(a);
    		if (check[1] == true)
    			ban(b);
    		if (check[2] == true)
    			si(c);
    	}
    }
    
    
    int main(){
    	deque<int>t1;
    	deque<int>t2;
    	deque<int>t3;
    	deque<int>t4;
    	make_top(t1);
    	make_top(t2);
    	make_top(t3);
    	make_top(t4);
    
    	int n;
    	cin >> n;
    	int t, chg;
    	for (int i = 0; i < n; i++){
    		cin >> t >> chg;
    		check(t1, t2, t3, t4, t, chg);
    
    	}
    
    	int ans = 0;
    	if (t1[0] == 1)
    		ans += 1;
    	if (t2[0] == 1)
    		ans += 2;
    	if (t3[0] == 1)
    		ans += 4;
    	if (t4[0] == 1)
    		ans += 8;
    
    	cout << ans << "\n";
    	return 0;
    }

    반드시 알아야 할 TIP!!

    # 문제를 풀 때 충분한 생각시간이 필요하다 -> 손 부터 나가지말자!!

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1120.문자열  (0) 2020.05.17
    1018.체스판 다시 칠하기  (0) 2020.05.04
    1057.토너먼트  (0) 2020.05.01
    1094.막대기  (0) 2020.04.26
    4948.베르트랑 공준  (0) 2020.04.25

    댓글 0

Designed by Tistory.