[백준] 15662 톱니바퀴 (2) (+14891 톱니바퀴)

www.acmicpc.net/problem/15662

15662번: 톱니바퀴 (2)

2020-11-21

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main15662 {
	public static int T;
	public static LinkedList<Integer> list[];
	
	public static void left(int num, int rot) {
		if(num-1 >= 0 && list[num-1].get(2) != list[num].get(6)) {
			left(num-1, -rot);
			rotate(num-1, rot);
		}
	}
	
	public static void right(int num, int rot) {
		if(num+1 < T && list[num+1].get(6) != list[num].get(2)) {
			right(num+1, -rot);
			rotate(num+1, rot);
		}
	}
	
	public static void rotate(int num, int rot) {
		if(rot == 1) list[num].addFirst(list[num].pollLast()); 
		else list[num].addLast(list[num].pollFirst());		
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int count = 0;
		T = Integer.parseInt(st.nextToken());
		list = new LinkedList[T];
		for(int i = 0; i < T; i++) list[i] = new LinkedList();
		
		for(int i = 0; i < T; i++) {
			st = new StringTokenizer(bf.readLine());
			String str = st.nextToken();
			for(int j = 0; j < 8; j++) {
				list[i].add(Character.getNumericValue(str.charAt(j)));
			}
		}
		
		st = new StringTokenizer(bf.readLine());
		int R = Integer.parseInt(st.nextToken());
		for(int i = 0; i < R; i++) {
			st = new StringTokenizer(bf.readLine());
			int n = Integer.parseInt(st.nextToken())-1;
			int r = Integer.parseInt(st.nextToken());
			
			left(n, -r);
			right(n, -r);
			rotate(n, r);
		}
		
		for(int i = 0; i < T; i++) 
			if(list[i].get(0) == 1) count++;

		System.out.println(count);
	}
}

 

1. 각각의 톱니바퀴의 상태를 링크드리스트에 입력을 받는다.

 

2. 회전 횟수 만큼 회전을 한다. 이 때, 번호의 값은 편의상 -1을 해주어 톱니바퀴를 0부터 세도록 한다.

left -> right -> current 순으로 회전을 한다.

 

3. left의 경우 회전해야하는 기준 톱니바퀴의 6번째 자석값과, 그 전 톱니바퀴의 2번째 자석값을 비교했다.

right의 경우 회전해야하는 기준 톱니바퀴의 2번째 자석값과, 그 다음 톱니바퀴의 6번째 자석값을 비교했다.

이 때, 처음 기준의 반대되는 방향으로 회전을 했다.

 

4. 맨 마지막에 기준 톱니바퀴를 받은 방향 값으로 회전을 했다.

 

---

1, 2번째 테스트 케이스만 맞고 다른 테스트 케이스가 안 맞아서 고민을 했었다. 처음에는 아래와 같이 잘못 코드를 짰다.

아래와 같이 코드를 짜게되면, 먼저 회전을 하고나서 전/다음 톱니바퀴랑 비교를 하기 때문에 데이터가 맞지 않는다.

public static void left(int num, int rot) {
	if(num-1 >= 0 && list[num-1].get(2) != list[num].get(6)) {
		rotate(num-1, rot); //잘못된 코드 순서
		left(num-1, -rot);
	}
}
	

 

그래서 아래와 같이 재귀 형태로 체크해서 회전을 할 수 있는 톱니바퀴들을 전부 체크한 후 맨마지막에 하나씩 rotate하니 맞았다.

public static void left(int num, int rot) {
	if(num-1 >= 0 && list[num-1].get(2) != list[num].get(6)) {
		left(num-1, -rot);
		rotate(num-1, rot);
	}
}
	

 

 

 

 

---

 

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

작년 초 쯤 풀었던 기억이 있다. 톱니바퀴(2) 문제와는 달리 톱니바퀴 갯수가 4개로 정해져있어서 하드코딩;;으로 풀었던 안 좋은 기억이 있다,,, 그 당시에는 지금 같은 생각을 못했었다...

 

그래서 지금과 같은 방식으로 다시 제출해봤다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main14891 {
	public static int T;
	public static LinkedList<Integer> list[];
	
	public static void left(int num, int rot) {
		if(num-1 >= 0 && list[num-1].get(2) != list[num].get(6)) {
			left(num-1, -rot);
			rotate(num-1, rot);
		}
	}
	
	public static void right(int num, int rot) {
		if(num+1 < T && list[num+1].get(6) != list[num].get(2)) {
			right(num+1, -rot);
			rotate(num+1, rot);
		}
	}
	
	public static void rotate(int num, int rot) {
		if(rot == 1) list[num].addFirst(list[num].pollLast()); 
		else list[num].addLast(list[num].pollFirst());		
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int count = 0;
		T = 4;
		list = new LinkedList[T];
		for(int i = 0; i < T; i++) list[i] = new LinkedList();
		
		for(int i = 0; i < T; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			String str = st.nextToken();
			for(int j = 0; j < 8; j++) {
				list[i].add(Character.getNumericValue(str.charAt(j)));
			}
		}
		
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int R = Integer.parseInt(st.nextToken());
		for(int i = 0; i < R; i++) {
			st = new StringTokenizer(bf.readLine());
			int n = Integer.parseInt(st.nextToken())-1;
			int r = Integer.parseInt(st.nextToken());
			
			left(n, -r);
			right(n, -r);
			rotate(n, r);
		}
		
		count += list[0].get(0) == 0 ? 0 : 1;
		count += list[1].get(0) == 0 ? 0 : 2;
		count += list[2].get(0) == 0 ? 0 : 4;		
		count += list[3].get(0) == 0 ? 0 : 8;

		System.out.println(count);
	}
}