내 소식

오르비

태그

내 태그
입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion
오르비 랭킹
XDK 누적 복권
XDK 경매
RARE

수능쎈츄 [1174003] · MS 2022 (수정됨) · 쪽지

2023-01-10 18:09:53
조회수 2,941

백준 2830번: 행성 X3(골드 III)

게시글 주소: https://dev.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)

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

수능쎈츄 [1174003]

쪽지 보내기

글쓰기
오르비 1455015번째 회원 되기
아이디 찾기 비밀번호 찾기

오르비 캐스트

오르비 과외시장

2027 수능 D - 99

오르비 플레이
오르비 RARE
Move
our corporate site
Orbi Class
on-line classes
Orbi Books
educational books & resources
Gae9
humor and fun

© 2000-2026 Move Inc.

orbisoptimus (v17-5e1090)