백준 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를 선물하세요.
-
-
눈온당 0
-
출석부! 출석부 출석부! 지하철! 지하철 지하철! 공산당! 공산당 공산당! 진짜...
-
스타킹 0
찢기
-
이시간에
-
불면증.. 4
원하는 기상시간보다 45분이나 일찍일어나버렸다
-
잘까 4
흠
-
안자면 큰일날듯 1
옯붕이들 ㅂㅂ
-
2차 얼버잠 2
이젠 진짜 ㅃㅃ
-
동서연고. 1
무요.. 왜요.. 혼잣말이에요..
-
다시 했을 때 메디컬 가능성 얼마나 보시나요?
-
잘때가된건가 5
슬슬
-
발 300 11
손도 많이 큼
-
꾸준히 햇으면 꽤나 올렷을거 같은데 오랜만에 하려니 계속 같은 곳에서...
-
ㅅ..ㅂ 요즘에도 한달에 한번은 뛰다가 무조건 삐는 것 같다
-
키작은 사람이 6
큰 사람보단 끌림
-
마스터 등반 시작
-
응..
-
재밋는건같이해요
-
귀가 ㅇㅈ 2
사실 아까 퇴근하면서 찍었어요
-
키작으면 좋은점 4
애들이 귀엽다고함 헤헤
-
ㅋㅋ 난 작년에 2
공부하는거에도 기출이 잇엇음.한국 기출만 봤을 때2008년도부터 2023년도 기출된...
-
새르비 화력 테스트 18
유동인구 10명 넘을까?
-
팩트는 0
마이 베스또 프렌드들은 몇시간째 디코를 하며 롤을 하고 잇다는거임.지금도 디코에...
-
굿모닝 1
ㄱㅁㄴ
-
-
에휴이
-
-
오르비 굿밤 2
전 자러감
-
서버 어머같네요 0
ㅎㅎ
-
-
맞팔 구합니다 3
현역학생입니다 물리러에요
-
ㅇㅂㄱ 1
수업가야겠군
-
연구원인데 떼잉,,삼각함수랑 수열을 훨 잘함 지로함에 비하면
-
ㅇㅈ 13
새벽이니까 다행일듯 내 손임 펑~~
-
학벌딸 치고 싶어서 인거 같음 그냥 병신 한남 자존감 밑바닥 루저새끼라 뭐라도 하나...
-
안 맞게 공부를 하고 잇음 ㅋㅋ,,내 공부 이론대로 하는 공부가 좀 상당히 피곤함....
-
내 차단리스트 1
없음뇨
-
응.. 부러워..
-
침대에서 자면서 망상함
-
지로함 6
평가원에선 잘 모르겟는데 (어렵게 안 내서), N제같은거 보면 되게 재밋는 문제...
-
무슨 이미 의대 붙은 것마냥 의대 성적 되면 의대를 갈까 설대를 갈까? 의대 가면...
-
수강 신청 0
막 20학점씩 신청 해놓고 나중에 빼는 방법 좋나요? 예상대로 안될 때가 많으니...
-
기출 좋앗던거 3
241122 (개 잘 만든문제)121130 (함수의 증가속도, 아주 중요한 관점)...
-
국회증언법이랑 양곡법 이런거 비판하는 내용있으면 너무 그렇지??..
-
롤의정리 4
롤은 재밌다
-
공군 질받 9
암거나 ㄱㄱ
-
잘자용 16
배가 고파져서 블아 ost 158번 그레고리오 피아노 버전을 들으면서 이만 자야겠오요
-
성대바꿔
-
롤할사람 4
모집ㅂ중
습격자 초라기 풀어보실
저리가요
DP 고트 문제임
그거 플레라 제가 아직 건들기에는DP 연습문제 몇개 던져주심 그거풀고 도전해봄