878A : Short Program

난이도

난이도는 어려웠다..? 애매하다.수학잘하는사람한텐 쉽나? 이런 유형이 많나?

근데 어렵다. 어려울려면 5/10,

나는 접근방법을 찾아내지 못했었지만...=.=

문제보기

http://codeforces.com/problemset/problem/878/A

내용이 긴데

입력받은 n줄에 걸쳐 c와 num을 받는다. 1<=n<=5*10^5, c={'&', '|', '^'}, 1<=num<=1023.

근데 해당연산을 같은 결과가 나오게 최대 5줄로 출력하고싶단다.

출력물은 짧은 연산횟수와 연산횟수에 걸친 "연산자 num" 을 출력하면된다.

다음 입력을 생각해보자.

3
| 3
^ 2
| 1

출력은

2
| 3
^ 2

로 나올 수 있다.

최대 5줄로 줄이라길래... 

어떤수 a에  (((a |3) ^2) |1)연산한것은 무엇과 같을까? 

((a|3)^2)와 같다. 그러나, 더 줄이면 (a|1) 과도 같다. 

더 줄이면 줄일 수록 좋은것인가? 이런 질문이 머릿속으로 난다.

정답은 애초에 5줄로 줄여 연산결과가 정답과 맞으면 되는, 

다양한 연산자 조합이 나타날 수 있다. 그러니까

3
| 3
^ 2
| 1

이라는 입력에는 이제까지 말한것고ㅏ 같은

5
| 3
^ 2
| 1
| 1
| 1

4
| 3
^ 2
| 1
| 1

3
| 3
^ 2
| 1

2
| 3
^ 2

1
| 1

과 같은 다양한 정답이 주어질 수 있다.
아무래도 정답은 문자열 그대로 체크하는 것ㅇ ㅣ아닌
출력해낸 문자열을 입력받아서 다시 연산하는 과정을 거치는 것같다.

문제 풀이

처음엔 이렇게 접근했다. 어음.... 

1) a, b, c 변수를 선언하고 |는 |연산대로, ^는 ^연산대로, &는 &연산대로... 결과값을 축적시킨다...

a는  |를 맡고, b는 ^를 맡고, c는 &를 맡고...  a, b 는 0으로 초기화하고, c는 1023으로 초기화했다. &연산자의 특징때문이다.

예를 들어설명하면.

3
| 3
^ 2
| 1

들어오면 

a|=3, a|=1, b^=2... 그럼 

print  (a>0) +(b>0)  + (c>0)// true false  

if (a)  print    | a
if (b)  print   ^ b
if (c)  print    & c

완벽해보이기도 했지만...

 엥근데 문제가 있었다. 연산자의 나오는 순서에 따라... 연산 수행순서에 따라. 연산결과가 다르기 때문인가? 확실히 & ^ &   와 ^ & &,  & & ^ 는 다르다..

5 & 1 ^ 2 & 3 == 3,    5 ^ 2 & 3 & 1 == 1 ,  5 & 1 & 3 ^ 2 == 3 흐음....

그리고 위의 알고리즘이라면 출력이 정해져있기때문에, 누적된 결과 즉

& 1, ^ 3,  |5 인경우 

출력이

& 1
^ 3
| 5  처럼 되는것과

| 5 
^ 3
& 1 처럼 되는것과 완전다르다는것이다.

2) 그래 그럼 걍 한 변수에 연산을 축적시키자. 그럼 어쨋든 결과값이 완성될거아니냐? 거기서 연산자를 유추해보자!!! 예로 초기값 1023을 잡아보자.

연산이 다음과 같이 들어왔다고하자

2
& 7
| 11 

2013  &  7  | 11  이니까 15이다. 그럼 

1
& 15

라고 출력하면되네 ㅋㅋㅋ 갸꿀 

그러나 여기에 문제가있다. 초기값 a에 따라 결과가 완전히 다르다는것이다.
예로

2
& 242
^ 1008

인 경우

7      & 242 ^ 1008
1000 & 242 ^ 1008 , 이 두연산의 결과는 확실히 다른것이다. 

연산을 수행하고나면 각각 1015, 784 이다.

순진하게 다음과 같이 출력하면 바로~ 탈락이다.

1
& 1015  또는.

1
& 784. 등이 나오겠지 뭐,

즉, 위처럼 출력하면 바로 탈락이다.

우리는 일반적인 a의 값에 대해 (a는 자연수이다 . 열라게 클 수있다.) 서도 일반화된 연산묶음으로 훌륭하게 묶어줘야한다..

아직 잘모르겠짖만 예를보자.

 a가 0이라고 하고 위에 예를 든 연산을 수행해보자. 0 & 242 ^ 1008 은 어쨌든 1008이다.

근데 내가 출력할 & 1015 는 결과값이 0이다. ㅎㅎ 망했다.

더 똑똑한 방법이 필요한데, 그렇다면 비트 연산자의 성질을 알아야한다. 나는 잘 몰랐으므로,

 

3) "아, 어쩌면 큐 용량 5인걸루 쓰고, & | | | | | ^^ ^^^ &&&& 이렇게들어오면, & | ^ & 이렇게 압축되지 않을까?, " 같은 생각을 하게 되었다.

아 그러면 팝해주면되니까 출력은 연산순위에 상관있게   & | ^ & 처럼 나오긴하는데, & | ^ & | ^ & ^ 이런식으로 나오면 어쩌지 ㅎ..? 무조건 중첩되게 입력이 주어진다라는 은밀한 논리인가

라고 생각해서 짜보았지만 깔끔하게 탈락...

왜냐하면 &  | ^ & | ^ ^ & | ... 이런 교차 입력이 들어왔기ㄸ ㅐ문이다 푸하하 ㅠ.ㅠ

4) 그럼 naive하게 논리 연산자를 분배법칙을 이용해(? 사실논리연산자가 분배법칙이 적용되는 것을 알면 당신은 순진하지 않지만.... )  어떡어떡하게 수학적 참의미를 알아버려 수십만개의 연산자가 들어와도 5개로 줄일수 있나? 라고 생각까지 해보았다.

결론은 다 망했다.

자자자자 

어쨌든 연산자마다 각 변수를 선정하고 연산을 축적시키는건 꽤 좋은생각같다. 

그러나 임의의 수 a에 대해 연산자, 숫자를 축적해야하므로 어떤 연산자를 살려야해서 출력할지 그것이 애매하다.

1) 첫풀이를 제시해본다 링크참조.  

https://www.acmicpc.net/board/view/19710

내가 고민을 많이해도 문제가 풀리지 않아, BoJ에 질문글을 남겼고 다행히 고수 분들 께서 도움을 주셨다.

사실 내가 앞으로 할 첫 번째 풀이보다 링크엔 더 자세하게 설명이 있지만, 또 내 나름대로 정리해보기 위해 해당 첫 번째 풀이 풀이를 기술해본다.

자자 문제를 풀기 위해선 우선 다음 명제들을 살펴보자.

Fact : 연산자 뒤에 따라오는 0~ 1023 의 자연수는 10자리의 이진수로 나타낼 수 있다.

Fact : and 연산자는 뒤에 따라오는 숫자의 0의 위치에 따라 반드시 그 자리는 0으로 바뀐다.

예)   10101 & 10001 = 10001

Fact : or 연사자는 뒤에 따라오는 숫자의 1의 위치에 따라 반드시 그 자리는 1으로 바뀐다.

예) 10011 | 00100 = 10111

Fact : xor 연산자는 앞 항의 수와 뒤 항의 수가 동일하면 0을 도출하고, 다르면 1을 도출한다.

예) 10011 ^ 00111 = 10100

Fact : or and 연산자는 기존 비트 (0, 1) 을 유지할 때도 있다. or의 경우는 뒤 항이 1일때는 반드시 앞 항을 1로 만들지만 뒤 항이 0일때는 앞 항의 비트가 그대로 유지된다.  10 | 00 = 10

and의 경우는 뒤 항이 0일 때는 반드시 앞 항을 0로 만들지만, 뒤 항이 1윌 때는 앞 항의 비트가 그대로 유지된다.  10 & 11 = 10

위 사실은 우리가 앞으로 할 논리의 힌트를 살펴 본것이다. 어떤 수가 들어오던 간에 해당 자리가 어떻게 변하게 되었는지 상태만 저장해놓으면된다.

이 상태는 4가지로 정리될 수 있는데 다음과같다

1) 어떤식으로 0이 되었거나 (and)

2) 어떤식으로 1이 되었거나 (or)

3) 맨 처음 임의의 수가 가진 비트를 그대로 가지게 되었거나. 

4) 맨 처음 임의의 수가 가진 비트를 반대로 가지게 되었거나. (xor)

비트들은 이 4가지 상태에서 왔다갔다 한다.

우린 이 풀이를 위하여 각 10자리의 비트수를 임의의 상태를 저장해볼것이다. (마치 오토마타처럼.)

비트의 상태 : 0~3 , 0: 0이된경우, 1: 1이된경우, 2: 초기상태, 3: 초기상태의 반전 비트로 할것이다.

우선 각 상태 배열을 생성하고 상태를 2로 초기화 해준다.

그 뒤 입력을 받는데, 연산자와 딸려오는 숫자 만큼 상태를 건드려준다.  & 인경우 뒤 항의 숫자를 비트로 바꾼 후 0만을 참고해서 다 0으로 만들어주고, | 인 경우 뒤 항의 숫자를 비트로 바꾼 후 1만을 참고해서 1로 바꾸어준다. xor인 경우 뒤 항의 숫자가 1인경우 상태를 바꿔준다. 왜냐하면 xor 연산자는 뒤 항 숫자가 1일 때만 앞의 숫자를 바꾼다. 잘 이해가 가지 않으면 진리표를 참고해보자

a    b    a xor b

1    1       0

1    0       1

0    1       1

0    0       0

아래는 상태를 처리해준 코드이다. 잘보면 xor 연산은 상태를 2에서 3으로(초기에서 xor적용), 3에서 2로(xor에서 또 xor적용), 또 1에서 0(or 1뒤에 xor처리)으로 또 0에서 1(and 0 뒤에 xor처리)로 바꾸어준다는 것을 볼수 있다.

그 외 or 연산과 and 연산은 오직 1 또는 0으로 상태를 바꾼다. 

상태는 대략

i=0 부터 i=9 까지 아래처럼 될 수 있다.

0 0 2 2 2 3 3 1 1 1    ( 주의, 배열 index이므로. 이진수와 높은자리가 반대임)

그렇담 우리가 할 수 있는것은

2^9, 2^8, 2^7 을 or 연산때리고,

2^0, 2^1 을 제외하게 and 연산 때리고

2^5, 2^6 을 xor연산 때리면된다.

그리고 나머지 비트에 대해선 건들지 않는다.

and, or, xor 연산은 각각 겹치지 않는 비트만을 건들므로, 정답 연산자 출력 순서에 하등관계없다.

전체코드는 다음과 같다.

input 이

3

^ 1

^ 2

^ 3 이 들어온 경우 어떨까?

2 2 2 2 2 2 2 2 2 .... 상태에서 ( 주의, 배열 index이므로. 이진수와 높은자리가 반대임)

3 2 2 2 2 2 2 2 2 ....

3 3 2 2 2 2 2 2 2 2 ....

2 2 2 2 2 2 2 2 2 2 ....

가 된다.

따라서 원래 임의의 수와 같다.

이 코드의 output은

3

| 0
& 1023
^ 0

이 된다.

자자자자자 두번째 풀이

첫번째 풀이를 보고왔으면, 어떠한 임의의 수가 들어오더라도 "뒤에 따라오는 수십만개의 논리 연산자가 있더라도" 초기 임의의 수의 어떤 비트가 변경되고 변경 안되는지를 따라서 연산해보면 수십만개의 논리적연산도 단지 3개의 논리연산자로 대체할 수 있음을 느꼈을 것이다.

      놀랍다

이전 풀이에서는 비트가 단지 0과 1의 상태만을 가지고 있지만, 해당 비트를 건들지 않았을 경우 + 해당 비트에 대해 짝수번에 xor 연산을 행한경우 상태 4가지를 정의해서 풀었다. 

그런데 잘 생각해보면은, 애초에 임의의 수라는게 해당 비트가 0 또는 1이다. 그래서 우리는 두 정수 변수 0과 1023을 선언해준뒤 따라오는 연산을 각각 축적해주고 비교만 해주면된다.

응 무슨소리야?

에,.. 그러니까 or 연산은 항상 해당 비트를 1로만들고 and 연산은 항상 해당 비트를 0만들잖아, 만약 문제에서 or 비트와 and 비트만 주어진다면 상태가 몇 개만 필요한지 알겠어? 

어... 음 3개? 

1)  해당 비트를 0으로 무조건 만들어라   2) 해당 비트를 무조건 1로 만들어라  3) 해당 비트를 초기로 유지하라 

그래 좋아, 그런데 이미 우리가 초기의 수 모든 경우를 쉽게 구현할 수 있는 경우라면? 그러니까 초기상태의 비트는 0 또는 1이잖아? 그니까 변수는 0000000000,  1111111111 의 상태일거야. 중간의 상태수 010101011, 1101011, 뭐 이런 것은 신경 쓸필요가 없어. 우리는 해당 자리수의 비트가 바뀌었나 안바뀌었나만 볼거니까.  000000.... 과 11111...로 모든 경우의수를 포함할 수 있어.

이 경우의 수를 모두 지닌채로, 해당 연산을 각각 모두 수행한뒤에 비교한뒤 둘다 해당자리가 1인 경우면 해당 자리에는 반드시 어떤경우에도 1인거니까 or 연산 때리면 되겟지? 해당 비트를 반드시 1로 만들면되니까. 둘다 0인경우는 해당 비트를 제외한 곳에 & 1 연산 떄리면 되지. 그럼 둘중 한곳에만 1이 잇는경우엔? 그땐 xor 연산이지. 초기에 0, 1 인데 각각 1, 0 으로 바뀐경우는 xor 말고 더 있겠어?

잘 이해가 안가도 봐봐,  두 초기 상태가 0000 1111라고 해보자.

그렇다면 결과값이 임의의 연산을 통해 각각 1100, 1010이 도출되었다고 하자. 

다음을 체크하면된다.

1) 두 비트 중 둘다 0인경우는 and 연산으로 0으로 만들어준다. 그니까 1100 1010 비교해보면 첫째자리가 0이잖아? 그럼 & 1110 때리면 첫번재 자리만 0이 되겠지.  "and 1110"

2) 두 비트 중 서로 상이하면서 초기 상태와 다른 자리를 xor 연산해준다. 1100과 1010가 있다고 해보자. 3째 자리와 2째자리가 다르지? 둘째자리는 각각 초기상태와 같아. 이경우 셋째자리만 xor 처리해주면되. 둘다 서로 다르면서 초기상태와 다른 자리를 어떻게 찾느냐고? 이건 내가 가르쳐줄게. 모두 1111 이였지만 결과값이 1010었던 것을 부정해보자. 0101 이잖아? 1100 & 0101 하면 셋째자리만 나와. "xor 0100" 

3) 두 비트 중 둘다 1인 경우는 or 연산을 때리자. 반드시 해당자리가 1이되어야하니까 or 연산을 하면된다. 1100 & 1010 하면 마지막 자리 4짜지리가 둘다 1이다. 그러므로 "or 1000" 

자자 이렇게 멋지게 풀었다. 세번째 풀이도 있는데, 그것은 & ^ 연산자만으로도 충분히 표현하는 것이다.

하지만 또 풀어야할 문제가 있으므로 잠깐 그것은 미룬다. ㅠ.ㅠ.

소스보기

1  https://github.com/ingyeoking13/algorithm/blob/master/cf/bitmask/878A.c

2 https://github.com/ingyeoking13/algorithm/blob/master/cf/bitmask/878A_2.c