Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 스터디
- 백준 4358번
- 리액트 네이티브
- 깃허브 토큰 인증
- 모두의네트워크
- 깃 터미널 연동
- HTTP
- 자바
- 네트워크
- 모두를위한딥러닝
- 머신러닝
- 팀플회고
- 딥러닝
- 모두를 위한 딥러닝
- 데베
- 리액트 네이티브 시작하기
- 깃허브 로그인
- 백준 4358 자바
- 백준 5525번
- SQL
- 백준
- 문자열
- 모두의 네트워크
- 깃 연동
- 정리
- 지네릭스
- 백준 4949번
- 리액트 네이티브 프로젝트 생성
- 데이터베이스
- React Native
Archives
- Today
- Total
솜이의 데브로그
백준 12931번 ) 두 배 더하기 (java) 본문
https://www.acmicpc.net/problem/12931
문제
풀이
이진수로 생각해서 풀어야 하는 풀이이다.
해당 숫자를 이진수로 변경하여 생각하면 *2 를 한느 경우는 이진수 자체를 < 연산하여 왼쪽으로 한칸 씩 옮기고 가장 오른쪽 자리에 0을 추가하는 것이고, +1 을 하는 경우에는 이진수 가장 오른쪽 자리를 1 올리는 것이다.
따라서 +1 한 횟수는 이진수의 1의 개수이고 *2 한 횟수는 이진수 길이 -1 이다.
전체 연산의 수는 +1 한 횟수 총합 + *2 한 횟수의 최댓값이다.
코드
import java.io.*;
import java.util.*;
public class BOJ_12931 {
static int answer, maxMultiply;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<N; i++) {
findAnswer(Integer.parseInt(st.nextToken()));
}
answer += maxMultiply;
System.out.println(answer);
}
static void findAnswer(int num) {
String binaryString = Integer.toBinaryString(num);
int bitCount = Integer.bitCount(num);
maxMultiply = Math.max(maxMultiply, binaryString.length() - 1);
answer += bitCount;
}
}
새로 알게 된 것
- Integer.toBinaryString : 10진수를 2진수 string으로 변환하는 함수이다. Integer.parseInt() 의 반대 역할
- Integer.bitCount : 이진수에서 1의 개수, 즉 true 값을 세어주는 함수이다.
진짜 기가막힌 함수들이다. 노가다로 다 개수 개산할뻔한걸 한번에 해결해주는 함수가 있다는걸 처음 알았다.
그리고 어떻게 이걸 보고 이진수 비트 연산으로 생각할 수 있을까? 더 많은 연습을 해야겠다.....!
'Algorithm > 백준' 카테고리의 다른 글
백준 2293번 ) 동전 1 (java) (0) | 2022.07.23 |
---|---|
백준 10026번 ) 적록색약 (java) (0) | 2022.07.23 |
백준 17298번 ) 오큰수 (java) (0) | 2022.05.27 |
백준 7576번 ) 토마토 (java) (0) | 2022.03.17 |
백준 24552번 ) 올바른 괄호 (java) (0) | 2022.03.17 |