백준 BOJ 2272 - 램프

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

2272번: 램프

아는분이 풀어서

나도 고민해서 풀어보았다

그분과 플래V 누가 먼저가는지 사소한 경쟁 중인데

열심히 노력해야겠다.

 

한칸 쉬프트연산(<<2 = *2) 후 xor 연산을 해주는것이 연산 방법의 핵심이고,

M이 엄청나게 커서 TLE가 나올 가능성이 매우 높은데

0line - 1
1line - 1 1
2line - 1 0 1
3line - 1 1 1 1
4line - 1 0 0 0 1
5line - 1 1 0 0 1 1
6line - 1 0 1 0 1 0 1
7line - 1 1 1 1 1 1 1 1

.

.

.

 

여기서

0, 2, 4번 line은 잘 보면

양쪽 끝이 1이고 나머지가 전부 0이다 => 2의 제곱수에 모두 적용된다.

이 특징을 잘 응용해주면

이분탐색처럼 수를 2의 제곱수로 쪼개서 문제를 해결할수있다.

 

#include <stdio.h>

//2line, 4line, 8line -> kline = 1 + 0 * (k-1) + 1 형태. 

int arr[1000000];
int tmp[1000000];

int main(){
	int n,m;
    scanf("%d %d", &n, &m);
    
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    for(int i=1; i<=m; i*=2){
    	if(i&m){
            for(int j=0; j<n; j++) tmp[j] = arr[j]^arr[(i+j)%n];
            for(int j=0; j<n; j++) arr[j] = tmp[j];
        }
	}
    for(int i=0; i<n; i++) printf("%d\n", arr[i]);
    return 0;
}

풀었다는 그분 소스도 봤는데

다 비슷비슷한거같아서 걱정이다.

다음부터는 누가짰는지 주석이라도 박아둘까 싶다.

 

덤으로 이 문제를 풀어서 랭크가 골드2까지 올라갔다.

더 노력해야지.