블로그 이사 중입니다 >> gumgood.github.io

2830 행성 X3 본문

Problem Solving/문제 풀이

2830 행성 X3

gumgood 2018. 11. 6. 15:09

C++11


거주민 이름을 2진수로 나타내면 최대 20자리


각 자리별로 1이 몇 번 나왔는지 count한다.



어떤 자리수를 봤을 때, 1인 사람과 0인 사람의 친밀도가 해당자리에서 1이 되므로


(1인 사람) * (0인 사람) 조합수만큼 친밀도의 해당 자리수가 1이된다.


(0인 사람) = n - (1인 사람)이므로


각 자리수별로 (1인 사람) * (n - (1인 사람))을 더하면 친밀도의 합을 구할 수 있다.


O(n)

'Problem Solving > 문제 풀이' 카테고리의 다른 글

5555 반지  (0) 2018.11.06
4880 다음수  (0) 2018.11.06
2830 행성 X3  (0) 2018.11.06
1946 신입사원  (0) 2018.11.06
1747 소수&팰린드롬  (0) 2018.11.06
10830 행렬 제곱  (0) 2018.11.06
0 Comments
댓글쓰기 폼