[백준] 25114번: Sequence Conversion Java

문제

You are given two arrays of non-negative integers a_1,a_2,…,a_N and b_1,b_2,…,b_N.

You can perform the following operation several times:

• Choose a non-negative integer x and an index 1≤i<N. Then change a_i to ai⊕x and change a_(i+1) to a_(i+1)⊕x.

Expression x⊕y means bitwise xor of two numbers x and y.
In binary representation, if the i-th digit of x and y is equal, then the i-th digit of x⊕y is 0, and if not, it is 1.
The given operation exists in all modern programming languages. For example, in C++ and Java, it is represented as x ∧ y.

You want to convert {a_i} to {b_i} by performing the minimum number of operations.

Find the minimum number of operations to convert {a_i} to {b_i}.

If you cannot convert {a_i} to {b_i} with the given operation, print −1.

 

입력

The first line contains an integer N, where N denotes the length of the two sequences.

The second line contains N space-separated non-negative integers a_1,a_2,…,a_N.

The third line contains N space-separated non-negative integers b_1,b_2,…,b_N.

 

출력

Print −1, if it is impossible to change the sequence {a_i} to {b_i}.

Otherwise, print the minimum number of operations needed to change the sequence {a_i} to {b_i}.

 

https://www.acmicpc.net/problem/25114

25114번: Sequence Conversion

접근

XOR 연산과 관련된 문제입니다.

a 배열을 b배열로 바꾸는 최소 횟수를 구하는 것인데, 방법은 다음과 같습니다.

a_i에 x라는 수를 xor 연산으로 변환한다면, a_(i+1) 에도 x와 xor 연산을 한다.

XOR 연산의 특징은

1) 2진수로 변환한 a와 b의 각 자릿수를 비교하여 같으면 1, 다르면 0 을 나타냅니다.

 ( 0^0 = 1, 1^0 = 0, 0^1 = 0, 1^1=1)

2) xor은 교환법칙, 결합법칙이 성립합니다.

3) x^y=z라면 y^z = x, x^z = y 입니다.

 

a_i번째를 x라는 수와 xor 연산을 통해 b_i로 바꾼다면,

a_(i+1)번째에도 x와 xor 연산을 해야합니다.

 

3)번의 특징을 이용하여 x를 구할 수 있습니다.

 

첫번째에서 (n-1)번째까지 a[i]와 b[i]에 대해 비교합니다.

만약 a[i]와 b[i] 다르다면,

연산 횟수를 증가시키고, xor 연산할 x를 구한 뒤 이를 a[i+1]와 xor 연산시킵니다.

 

연산이 종료되었을 시,

n번째 a의 수와 n번째 b의 수가 일치하면 연산 횟수를 리턴하고,

불일치라면 -1을 리턴합니다.

구현

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

public class Main {
	//https://www.acmicpc.net/problem/25114
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//배열 길이
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine());
		//a 배열
		long[] befores =new long[n];
		//b 배열
		long[] afters =new long[n];
		//값 입력
		for(int i=0;i<n;i++) {
			befores[i]=Long.parseLong(st.nextToken());
		}
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			afters[i]=Long.parseLong(st.nextToken());
		}
		//연산 횟수
		int count=0;
		//탐색, i번째 연산은 i+1에 영향을 주기에 n-1번째까지만 반복
		for(int i=0;i<n-1;i++) {
			long before = befores[i];
			long after = afters[i];
			//전과 후가 다르다면
			if(before!=after) {
				//횟수 증가
				count++;
				//xor 할 x 구하기
				long x = before^after;
				//변환 전의 i+1에 x와 xor 연산
				befores[i+1]^=x;
			}
		}
		//마지막 수가 일치되지 않았다면 -1
		if(befores[n-1]!=afters[n-1]) {
			count=-1;
		}
		//출력
		System.out.println(count);
		br.close();
	}
}