[BOJ] 18222번 투에-모스 문자열 (Java)
문제
풀이
접근
설명
1과 0을 1과 -1이라고 생각하자! ( 부호의 차이로 생각하자! )
2의 제곱 수(2,4,8,16,...)만큼 앞뒤로 대칭되고 있는 문자열!
즉, N보다 작은 2의 제곱수를 뺀 인덱스 값(N - (2*?)) 을 알면 N의 값을 알게 됨
위의 예시로 설명하자면, 27번째 값은 11번째 값과 같음(부호만 반대)
11번째 값은 3번째 값과 같음 ... 이 반복됨 => 재귀!
즉, N보다 작은 2의 제곱수를 뺀 인덱스 값을 찾으며 재귀를 타고 1이 됐을 때에 0을 리턴해준다.
이때 한번 재귀를 돌때마다 0은 1로, 1은 0으로 변환해야하기 때문에, 1에서 리턴받은 값을 빼주어 간단하게 구해준다!
코드
더보기
import java.util.*;
import java.io.*;
public class Main{
static int res = 0;
static long[] pow; // 2의 제곱수들을 저장해 놓는 배열
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
pow = new long[64];
pow[0] = 1;
for(int i = 1 ; i < 64 ; i++){
pow[i] = pow[i-1]*2;
}
System.out.println(toemos(n));
}
private static int toemos(long n) {
if(n == 1){
return 0;
}
for(int i =0 ; i < 64 ; i++){
if(pow[i] >= n) return 1 - toemos(n - pow[i-1]);
}
return 0;
}
}
Author And Source
이 문제에 관하여([BOJ] 18222번 투에-모스 문자열 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-18222번-투에-모스-문자열-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)