[백준, Java] 13710번, XOR 합 3(비트마스킹, 누적합)

ㅏㅈ문제 링크

13710번: XOR 합 3

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 수열 XOR 합은 수열에 들어있는 모든 원소를 XOR한 값이다.

2. 수열 A가 주어질 때 모든 연속하는 부분 수열의 XOR합을 더한 값을 결과로 출력합니다.

3. 수열에는 1,000,000,000이하의 정수입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 연속하는 부분 수열의 XOR 합을 계산합니다.

 

3. 계산을 통해 얻은 XOR 합을 결과로 출력합니다.

 

XOR 합 계산하기(비트 마스킹, 누적합)

 

먼저, 연속하는 수열의 정보를 파악하는 방법에 대해서 알아보겠습니다.

 

 

수열 = { 1, 2, 3 }이 존재할 때 연속하는 수열의 정보를 파악하면

 

수열의 마지막이 1일 때

 

{ 1 }

 

수열의 마지막이 2일 때

 

{ 1, 2 }, { 2 }

 

수열의 마지막이 3일 때

 

{ 1, 2, 3}, { 2, 3 },  { 3 }

 

 

즉 연속하는 수열은 { 1 } , { 1, 2 }, { 2 }, { 1, 2, 3 }, { 2, 3 }, { 3 }

 

연속하는 수열을 구할 때 이전 수열의 값에서 현재 수열의 값을 추가하는 규칙을 보실 수 있습니다.

 

{ 1 }에서 { 1, 2 }, { 2 }으로 숫자 2가 붙어있는 것을 확인하실 수 있습니다.

 

위 부분수열의 대해서 XOR의 합을 진행한다면 아래와 같이 표현될 수 있습니다.

 

수열의 마지막이 1일 때

 

{ 1 }

 

수열의 마지막이 2일 때

 

{ 1^2 }, { 2 }

 

수열의 마지막이 3일 때

 

{ 1^2^3}, { 2^3 },  { 3 }

 

※ ^ : XOR 연산

 

문제에서 주어지는 연속하는 XOR의 합 : { 1 } + { 1 ^ 2 } + { 2 } + { 1^2^3 } + { 2^3 } + { 3 }

 

각 줄마다 현재 수열의 값이 붙는 규칙을 XOR 점화식으로 표현하면

 

수열의 마지막이 1일 때

 

{ 1 }

 

수열의 마지막이 2일 때

 

1^2 + 2 = (1 + 0)^2

 

수열의 마지막이 3일 때

 

1^2^3 + 2^3 + 3 = (1^2 + 2 + 0) ^ 3

 

 

하지만, 실질적으로 계산하면 1^2^3 + 2^3 + 3  != (1^2 + 2 + 0) ^ 3으로 식이 성립되지 않는다.

 

왜냐하면, 괄호를 먼저 합으로 계산하면 자릿수가 올라간 뒤에 XOR 3을 진행하게 되기 때문에 동일하지 않습니다.

 

XOR의 연산

a	b	a xor b
0	0	0
0	1	1
1	0	1
1	1	0

두 비트가 달라야 1이 나오는 규칙이 존재합니다.

 

그래서, 각 수열의 XOR 연산을 진행하기 전, 각 자릿수에 1, 0이 몇 개가 존재하는지로 표현할 수 있습니다.

 

(1010 + 1111) ^ 10을 진행한다면

 

(2121) ^ 10으로 변경이 가능하다.

 

2121에서 각 수가 정의하는 의미는 해당 자릿수에 1의 개수를 표현한다는 것입니다.

 

2121에서 가장 1번째 2는 4번째 자리에 1이 2개가 존재한다는 의미이다.

 

2121 ^ 0010으로 변경하여 진행하면

 

(1000 ^ 0000) * 2 =  1000 * 2 = 16

 

(100 * 000) * 1 = 100 * 1 = 4

 

(10 ^ 10) * 2 = 00 * 2 = 0

 

(1 ^ 0) * 1 = 1 * 1 = 1

 

16 + 4 + 0 + 1 = 21이 됩니다.

 

위의 식을 유심히 살펴보면 규칙이 존재합니다.

 

XOR을 진행하는 값이 1일 때 : 현재 수열의 크기 - 1의 개수

► 20 ^ 10 = 2(현재 수열의 크기) - 2(1의 개수) = 0

XOR 1을 진행하면 0인 값이 1이 되어야 하기 때문입니다

 

XOR을 진행하는 값이 0일 때 : 1의 개수

► 2000 ^ 0000 = 2(1의 개수)

XOR 0을 진행하면 1인 값이 1이 되어야 하기 때문입니다.

 

위에서 설명한 연속하는 수열과 XOR 연산을 진행하는 방법을 합치면 아래와 같습니다.

 

수열의 마지막이 1일 때

1 = 1

 

수열의 마지막이 2일 때

1^10 + 10 = (1 + 0)^10

(1 + 0) = 01

 

01 ^ 10

00 ^ 10 = 2(수열의 크기) - 0(1의 개수) = 2

 

1 ^ 0 = 1(1의 개수) = 1

 

21 = 2 * 2 + 1 * 1 = 5

 

수열의 마지막이 3일 때

1^10^11 + 10^11 + 11 = (1^10 + 10 + 0) ^ 11

 

(1^10 + 10 + 0)  = 수열 마지막 2일 때와 동일 = 21

 

21 ^ 11

 

20 ^ 10 = 3(수열의 크기) - 2(1의 개수) = 1

 

1 ^ 1 = 3(수열의 크기) - 1(1의 개수) = 2

 

12 = 1 * 2 + 2 * 1 = 4

 

모든 연속하는 수열의 XOR 합은 1 + 5 + 4 = 10

 

※ 예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 2

 

수열 : { 1, 2 }

 

 

2. 연속하는 부분 수열의 XOR 합을 계산합니다.

 

수열의 마지막이 1일 때

1 = 1

 

수열의 마지막이 2일 때

1^10 + 10 = (1 + 0)^10

(1 + 0) = 01

 

01 ^ 10

00 ^ 10 = 2(수열의 크기) - 0(1의 개수) = 2

 

1 ^ 0 = 1(1의 개수) = 1

 

21 = 2 * 2 + 1 * 1 = 5

 

연속하는 부분 XOR의 합에 대한 합은 = 1 + 5 = 6

 

 

3. 계산을 통해 얻은 XOR 합을 결과로 출력합니다.

 

계산을 통해 얻은 6을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해서 수열의 정보를 띄어쓰기 기준 나누었습니다.
• 누적합 및 1의 개수에 따른 XOR 점화식을 기준으로 각 수열이 마지막 수일 때 XOR 합을 구하는 getNxtPre을 실행합니다.
• getNxtPre 함수로 얻은 비트형식의 XOR값을 10진수로 변경하여 결과값에 더합니다.
• 모든 계산이 끝난 뒤 얻은 모든 부분 수열의 XOR 합을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• getNxtPre함수는 누적합과 XOR 점화식을 기준으로 현재 마지막이 되는 수 기준으로 XOR의 합을 비트형식으로 계산합니다.
• getNxtNum함수는 XOR a을 진행할 때 a가 1, 0일 때 점화식을 적용하는 함수입니다.
• getBit함수는 10진수를 2진수의 형태로 변경합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    //입력값 처리하는 BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //결과값 출력하는 BufferedWriter
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int n = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine()," ");
    //수열의 첫 번째 수 저장
    int first = Integer.parseInt(st.nextToken());
    //수열의 XOR 합 저장할 변수
    long result = first;
    //누적합을 진행하기 위해 이전 XOR 합에 대한 bit값
    List<Long> pre = getBit(first);
    //2번째부터 연속하는 부분 수열의 계산 진행.
    for(int i=2;i<=n;i++){
      int num = Integer.parseInt(st.nextToken());
      //현재 이진수 변환
      List<Long> binary = getBit(num);
      //이전 XOR합과 현재 이진수를 통해 XOR 합 구하기.
      List<Long> nxtPre = getNxtPre(pre, binary, i);
      long mul = 1L;
      //현재 XOR합을 결과값의 저장
      for (Long count : nxtPre) {
        result += count * mul;
        mul *= 2;
      }
      //이전 XOR합의 값 변경
      pre = nxtPre;
    }
    //모든 부분 수열의 XOR의 합 BufferedWriter 저장
    bw.write(String.valueOf(result));
    bw.flush();		//결과 출력
    bw.close();
    br.close();
  }

  // 부분 수열의 XOR 합 적용하는 함수
  private static List<Long> getNxtPre(List<Long> pre, List<Long> binary, int idx) {
    List<Long> nxtPre = new ArrayList<>();
    int preSize = pre.size() - 1;
    int binarySize = binary.size() - 1;
    if(preSize > binarySize){
      for(int j=0;j<=binarySize;j++){
        nxtPre.add(getNxtNum(pre.get(j), binary.get(j), idx));
      }
      for(int j=binarySize+1 ;j<=preSize; j++){
          nxtPre.add(pre.get(j));
      }

    }else{
      for(int j=0;j<=preSize;j++){
        nxtPre.add(getNxtNum(pre.get(j), binary.get(j), idx));
      }
      for(int j=preSize+1;j<=binarySize;j++){
        if(binary.get(j) == 1){
          nxtPre.add((long) idx);
        }else{
          nxtPre.add(0L);
        }
      }
    }
    return nxtPre;
  }

  //XOR a에 대해서 1, 0일 때에 따른 계산
  static long getNxtNum(long pre, long cur, int idx){
    if(cur == 1){
      return idx - pre;
    }
    return pre;
  }
  //10진수 2진수로 변경하는 함수
  static List<Long>getBit(long num){
    List<Long>bit = new ArrayList<>();
    while(num>0){
      bit.add(num%2L);
      num/=2;
    }
    return bit;
  }
}