논리화학 [746146] · MS 2017 (수정됨) · 쪽지

2022-05-22 06:24:50
조회수 7,083

수학) 221121 : -1을 허용한 이진법 풀이

게시글 주소: https://mission.orbi.kr/00056780095

이진법을 잘 모른다면 못읽을 칼럼인데, 딱히 이진법이 뭔지 설명하긴 귀찮으니 모르면 패스해도 됨.

단 이진법은 교과외니 안배우겠다 이딴소리 말고, 솔직히 이번 문제는 그렇다 치고 예전 문과 21번에 대놓고 이진법적인 추론 나왔는데 이쯤되면 얌전하게 공부하는게 맞음.


수열은 나열도 중요하나 분명히 발상도 중요함.

수능에서 두 번 넘게 나온 주제면, 당연히 알아야한다고 생각.



(시작)

일단 준 수열이 전부 양수인 상황은

이진수 표현으로

11111111110(2)이다.


이진법 표현으로 111(2)는 2^3-1=7인건 잘 알테니

저건 2^11-1-1=2046임을 알 수 있다.

아무튼 음수를 허용한 이진수는 무슨뜻이냐면


예를 들어


(-1)1111111110(2)의 표현을 허용한단 이야기.

이 경우, 원래 다 합쳐서 2046인데, 맨 앞 비트인 1024가 두번 빼지므로, -2가 될 것임을 알 수 있다.


다른 예시 하나로, 111(2)는 7이고

1(-1)1(2)는 7에서 2를 두 번 빼야하니 3이다.


이 문제에서 요구하는 수열의 이진수 표현은 다음과 같은 특징을 가진다.


1) 11자리 이진수이다.

2) 마지막 비트(1의 자리)는 0으로 고정이어야 하고, 나머지 비트의 값이 1 또는 -1이어야 한다.

(an들의 절댓값은 2^n으로 고정되어 있으므로)


여기서 잘 생각을 해 보자.


풀이1)



이 풀이는 직관과 이진법 논리의 활용이다. 직관이라 했으나 논리적 귀결은 완전함.


111(2)는 1000(2)보다 클 수 없다.

즉 n자리 이진수는 항상 n+1자리 이진수 보다 작다.


이 문제에서 수열의 합은 음수이다.


따라서 첫 비트가 -1이어야 전체 합이 음수가 될 것임을 쉽게 알 수 있다.


그게 앞서 언급한 수 (-1)1111111110(2)이다.

이 수의 값을 구할때, "두 번 뺀다"고 했다. 당연히 비트 1짜리를 비트 -1로 만들었으니 해당하는 비트 값을 두 번 빼줘야 한다.


위 수가 -2인데, -14가 되려면 -12가 남았다.

그러면 이진법 표현으로 6(110)에 해당하는 비트들을 -1로 치환하면 -12가 빼지고, 답을 얻는다.

즉 뒤에서 둘째비트(a1), 뒤에서 셋째비트(a2)를 -1로 바꾸면 된다.


(-1)1111111(-1)(-1)0(2)가 정답이다.




풀이2)


이 상황을 일반화해서 얻은 풀이법이다. 풀이 (1)이 더 좋으나, 이것도 참고해 보자.


일단 -14는 음수 허용 이진수로, 

0000000(-1)(-1)(-1)0

임은 쉽게 안다.


답을 구하려면 0을 지우면 되지 않을까?


0(-1)의 다른 표현은 (-1)1이다.


이거면 충분하다! 

 -14를 처음부터 음수비트로 표현하고, 쫘라락 올려보자.


0000000(-1)(-1)(-1)0

000000(-1)1(-1)(-1)0

00000(-1)11(-1)(-1)0

이쯤되면 그냥 -1을 계속 올리면 된다는 것을 깨달을 수 있고,


(-1)1111111(-1)(-1)0이 정답이다.


-2+8+32+128+512=678.

rare-다꼬리드디어세계지배 rare-Python

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.