-
Codeforce #515 Binary Numbers AND SumProblem_Solving 2018. 10. 28. 14:06Codeforce #515 Binary Numbers AND Sum
문제설명입력 조건2개의 이진수 자리수 n,m자리수 만큼 이진 수가 들어온다.이진수 a 와 b를 and 연산 한 값을 구한 뒤 b를 오른쪽으로 shift연산을 한다.다음 a와 이전에 b를 오른쪽으로 shift 여산한 값을 and연산 한 값을 구한뒤 현재 b를 shift한다.b가 더이상 shift할수 없을 때 까지 반복한다.
문제 풀이1 step이진수 a를 전처리 한다.
전처리 방법은 누적합을 구한다.ex)이진수 1010이 주어지면 비트가 켜신곳에 2의 지수승을 더하고 이전 인덱스에 최종적인 합을 누적해서 보관한다.만약 b의 이진수 길이가 더 클경우 부분합 배열을 b의 이진수 길이 만큼 구한다.위의 배열의 값은 첫 번째 자리수에서 현재 인덱스 까지 이진수 a의 켜져 있는 비트를 누적한 값이다위의 정의가 중요하니 꼭 상기 시키고 다음 스텝으로 넘어간다.2 step위 화살표로 표신 되어 있는 구간이 이진수 b가 켜져 있을 때 켜져 있는 a비트들과의 합들이 우리고가 구하려는 값에 더해질 수 있다.
우리는 1step에서 미리 구해 놓은 배열이 이진수 a의 켜져있는 비트의 합을 미리 구했기 때문에 부분 똑같은 연산을 중복으로 할 필요가 없으므로 해당 부분합을 그대로 더하면 된다.
소스 코드'Problem_Solving' 카테고리의 다른 글
Codeforce #521 Div3 E. Thematic Contests (0) 2018.11.18 Array Manipulation (0) 2018.11.11 BOJ 16236 아기상어 (0) 2018.10.27 BOJ 2479 계단오르기 (0) 2018.10.25 boj11505 구간 곱구하기 (0) 2018.10.25 댓글