8741번: 이진수의 합

8741번 이진수 합

8741번 이진수 합 클릭시 문제로 이동

1) 문제

---

2) 문제 설명

임의의 자연수 K가 주어진다. 

이진수의 K번째 자리수 이하의 모든 자연수의 합의 이진수 표기는?

ex) k = 3이면 이진수 3자리로 표현할 수 있는 수들의 합이므로

000 = 0, 001 = 1, 010 = 2, 011 = 3, 100 = 4, 101 = 5, 110 = 6, 111 = 7이므로

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

28의 이진수 값은 11100

---

3) 풀이 과정

이진수의 K번째 자리수 이하의 수로는 표현 못하는 가장 작은수는이다.

(2진수 표현법으로 K+1번째 수이므로 )

즉,

---

4) 핵심

! 를 계산할 수 있는가?

물론 계산은 할 수 있지만 엄청난 시간이 걸린다.

그러면 시간제한이 1초인데 당연히 틀릴 것이다.

즉 K의 범위 (1≤ K ≤ 1,000,00)안에서 3)풀이과정에서 구한 식

을 직접 계산을 하는 방법은 사용할 수 없는 것이다.

!!이진수로 를 표현하면 몇자리 수 일까?

10진수를 2진수로 표현하면

꼴로 나온다.

은 n+1자리수를 가진다는 의미이다.

는 20001자리수가 1이고 나머지는 0인 수이다.

즉 을 이진수로 표현하면 적어도 20001자리수 이하로 표현된다는 것이다.

을 이진수로 표현해보자

일단 을 이진수로 표현하면 2K번째만 1인 이진수이다.

을 이진수로 표현하면 K번째만 1인 이진수이다.

두 수를 뺀다면 2K-1부터 K번째까지 1인 이진수가 될 것이다.

ex) K = 4일경우

 1000 0000

-0000 1000

=0111 1000

즉 1이 2K-K = K개있고 이후에 0이 K-1개 있는 이진수가 되는 것이다.

※ 입력 범위를 생각하고 표현 방법을 바꾸는게 핵심이다.

---

5) 핵심 코드

1 2 3 4 5

int K = 0;       cin >> K;       cout << string(K, '1') << string(K - 1, '0') << endl;

cs

---

6) 기타

string 생성자를 사용하기 위해서는 #include<string>을 해주어야 합니다.

최대한 쉽게 설명한다고 풀어쓰고 있어서 더 난잡해 보일 수도 있습니다. ㅠ

읽기 불편한 부분이나 이해가 되지 않는 부분은 댓글 주시면 수정하겠습니다.

다른 알고리즘이나 다른 의견이 있으시면 댓글 주시면 감사하겠습니다 :)