백준 2830번: 행성 X3(골드 III)
게시글 주소: https://orbi.kr/00061232226
https://www.acmicpc.net/problem/2830
상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다. 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다. 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다. 이 결과 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다.
예를 들어, 10과 19의 친밀도는 25이다.
행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행성의 가치를 구하는 프로그램을 작성하시오.
첫째 줄에 X3 거주민의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 다음 N개의 줄에는 거주민의 이름이 주어진다. 이름은 1,000,000보다 작거나 같은 자연수이다. 첫째 줄에 행성 X3의 가치를 출력한다.
2020년에 처음풀고 갖다 버린(당시 고1) 문제입니다
제 프로필을 누르면 나오는
시도했지만 맞지 못한 문제
를 없애려는중 첫타자로 걸렸죠
한 이틀? 고민한거 같네요
핵심은 O(N^2)로는 절대 시간안에 통과하지 못하므로 O(N)이나 O(NlogN) 알고리즘이 있을거라 믿었습니다
수학적 증명은 코드 밑에 있으니 심심하면 읽어보세요
#include <stdio.h>
#include <math.h>
long long sum=0;
int b[21];
int main()
{
int N,i,n,k=1;
scanf("%d", &N);
for(i=0; i<N; i++)
{
scanf("%d", &n);
_10to2(n);
}
for(i=0; i<20; i++)
sum+=(long long)pow(2,i)*(N-b[i])*b[i];
printf("%lld", sum);
}
void _10to2(int x)
{
int i=0;
while(x)
{
b[i]+=x%2;
x/=2;
i++;
}
}
증명: n개의 수가 있고 10진수를 2진수로 변환했을때 2^0 부분이 1인 수가 x개라 치자.
이때 친밀도의 가짓수는 n(n-1)개이다. 이대로 돌리면 100% 시간초과로 터지니 다른 방법을 고안해보자.
xor연산을 하면 서로 다를때 1이다.
1. 1일때
나머지 1의 개수 = x-1개
->얘네는 전부 0됨
따라서 1일때 1나오는 개수는 y개
2. 0일때
0일때 1나오는 개수는 x개
따라서 xy + yx = 2xy인데
이게 중복된 결과이니 /2를 해주면 xy
각 자릿수를 곱해주면 i=0에서 19까지 2^i * x * y를 다 더해주면 답
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
나 잔다 ㅂㅂ
-
크아 6
크ㅜ
-
출근길에 방문열어봣다가 없어진거알면 뒤집어질거같아서 못가겟슨
-
야옹
-
남자들의 모순점 6
롤하는 여자를 찾지만 막상 롤창 여자 보면 신기해하거나 피함
-
알바 끝내고 새벽에 불교를 복습하며...
-
뭔가 근데 처음부터 여붕인걸 눈치까면 그냥 그렇구나 하겠늗데 14
남르비인줄알고 드립을 다 쳐놨는데 여르비라고 실토하면 배신감이 와..
-
놀랍게도 실화임.. 오르비에서 책 사면 주는 스티커 붙이고 다님뇨
-
무조건 달고 다닐 수 잌ㅅ음
-
내가하면 다들 나를 거르겠지
-
고향에 온거 같음
-
아 ㅈ같다 0
대리 이 ㅂㅅㅅㄲ는 갠새이 게속ㅊ쳐 넣노 일 ㅈㄴ 하기싫다 퇴근 언제하냐
-
자러갑니다 2
다들 좋은새벽보내시고 꿈 잘꾸시길 전 어제 운전하다가 총맞는꿈꿨음
-
이거 재밋네 다른 것도 해봐야지
-
F식 화법 6
무슨일 있어? 밥먹으러 갈까? 이거 아님?
-
자러간다 3
-
배고파 0
뭐 먹지
-
과외 날먹도 못 하겠고 컨텐츠 팀 일도 적당히 못 하겠어서 계속 수정하고...
-
확통런할까요 0
예비고3인데 작수 공통 20,21틀 미적 28 29 30틀입니다 이유도 말해주세용
-
으하하
-
금수저 부러워
-
현실이랑 넷?상 0
나는 여기서 교양인인척하고 현실에서는 노미현코스프레하고다님...
-
차이점은 넷상은 산화당한팀06오르비언을 둘째달에 보니까 3
그담부터 순화한 5번은 하고 돌려서 하는듯
-
전 ‘그건 나라도 ~하겠다.’ 이정도가 최대인데
-
이차곡선 슥삭해야지
-
현실이 없고 넷인생 넷친구만 있는데 어떡하나요?
-
극 내향인이라 롤보도 안킴
-
인터넷이 현실이고 현실이 인터넷이야
-
무지막지한거 가튼데
-
하..
-
개억까미친
-
뭐지…? 15
덕코 빠져나갔길래 뭔가 했는데 저 레어 머임..? 산적 없는데..? 아 뭐야 저거..
-
오..
-
깜짝 놀라는 것도 느리고 채팅도 느리고 생각도 느리고
-
미적 노잼임
-
부모님은 듣고싶은수업 다 들으라하시는데 이것도 성적으로 되돌려드리면 좋아하시나요?...
-
아이고빌런이되어있네 아이고
-
나를 위해 만들어진 프로그램..
-
옵만추하실분 4
옵붕이 만두먹이고 추노하기
-
신기하다는거물론 계속 잇는 사람들도 잇지만
-
아무나 구해요
-
야식머글까 8
잠안오니 배고프다
-
인스타에서 수학하는땅우랑 마이린 차단함
-
사실 전 차단 0
부러운사람 차단함
-
근데 무서울 뿐이야 2명 정도 있음
-
키 160대남자한테
-
머하지
-
미적분 질문 1
첫번째 사진에서 제가 쓴 식대로 연산 어디가 틀린건가요? 그리고 해설지 4번째...
-
찾아봐야지
-
1년햇는데 이정도면 적은건가
습격자 초라기 풀어보실
저리가요
DP 고트 문제임
그거 플레라 제가 아직 건들기에는DP 연습문제 몇개 던져주심 그거풀고 도전해봄