문제 링크
들어가기 전에
즉, X는 처음에 "0"으로 시작하여 "01"이 되고, "0110"이 되고, "01101001"이 되고, ⋯ 의 과정을 거쳐 다음과 같이 나타내어진다.
이 수열의 성질은, 위에서 써져있듯 이전 배열을 반전시켜서 새로운 수열을 쌓아가는 것이다.
즉, 무한한 수열의 어느 한 녀석 (예를 들어 4 번째 녀석) 의 값은 이것을 반으로 자른 값의 반대이다. (4번째 녀석을 2로 나누면 2번째 녀석, 그리고 이 녀석은 항상 4번째 녀석의 반대값이다)
정말인지 확인해보자
- 0
- 01
- 0110
4번째 녀석 : 0, 반으로 나눈 녀석(2번째 녀석) : 1
그렇다면, 여기서 한번 더 나눠보자
2번째 녀석 : 1, 2번째 녀석을 반으로 나눈 녀석 : 0
오! 그렇다면 3번째 녀석은 어떻게 구해야 할까?
우리는 "반으로 나눈다" 는 말이 x를 x /= 2 로 만든다는 사실을 알고 있다. 그리고 나눈다는 것은 즉, 그 만큼을 제외시킨다 라는 의미이다
3보다 더 큰 수열에서만 3을 찾을 시도를 할 것이므로, 수열을 다시 살펴보자
0110
여기서 세 번째 녀석은 1이다. 이 녀석은 01 / 10 으로 나뉜 수열의 0번 인덱스이고, 이것의 대칭의 0번 인덱스는 0이다
즉, 이 모든 값들은 "맨 처음 시작하는 0,1 중 하나로 돌아온다". 왜냐면 이진수의 반복이므로.
자르고 잘라서 2개씩 쭈루룩 나열했을 때 대칭값은 "01" 이라는 시작하는 녀석들로 돌아오게 된다.
코드로 보자
그래, 시작하는 01 이라는 값으로 무한히 돌아오는 녀석을 만들어야 한다.
2진수로 넓게 펼쳐진 녀석들 01101001... 의 "길이" 를 담은 2의 제곱승 배열을 선언하고
배열에서 주어진 길이보다 더 큰 값이 발견된다면 ex ) 주어진 값 10 : 2의 4승 16
그 순간, 2의 3승 (i-1)을 k에서 뺀 후 재귀를 돌려가는 형태. 이러면 "절반 나눠서" , "01로 돌아가는" 형태로 나아가게 된다
static class BOJ18222{
static long[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(br.readLine());
arr = new long[65];
arr[0] = 1; // 초기화
for (int i = 1; i < arr.length; i++) {
arr[i] = arr[i - 1] * 2; // 2씩 제곱
}
System.out.println(recur(N));
}
static long recur(long N){
if (N == 1) return 0;
for (int i = 0; i < arr.length; i++) {
if (N <= arr[i]) return 1 - recur(N - arr[i - 1]); // 더 큰 녀석을 찾았으므로, 더 작은 놈을 불러와서 재귀돌리기
}
// <1뎁스>
// 10 이라면
// for 문에서 i == 4 일때 (즉, arr[i] == 16 일 때 이프문 걸림)
// 걸린 후에 arr[i - 1] == 8 을 뺀 k의 값을 재귀로 돌림. 2뎁스로 들어간다
// <2뎁스>
// 2 라면
// for문에서 i == 1 일때 (즉, arr[i] == 2 일때 이프문 걸린다)
// 걸린 후에 arr[i - 1] == 1 을 뺀 k 의 값을 재귀로 돌림. 3뎁스로 들어간다
// <3뎁스>
// 1 이므로, 0을 리턴한다 -> 2뎁스로!
// <2뎁스>
// 재귀 recur() 로 리턴받은 값은 0이다. 따라서 1 - 0 의 값인 1 을 1뎁스로 리턴한다
// <1뎁스>
// 재귀 reucr() 로 리턴받은 값은 1이다. 따라서 1 - 1 의 값인 0을 리턴한다. 답은 0
return 0;
}
}뎁스별 설명 (재귀 부분)
N == 10 의 경우
1. 맨 처음 값을 찾기 위해, 재귀형태로 "들어가는" 부분
<1뎁스>
N == 10 이라면
for 문에서 i == 4 일때 (즉, arr[i] == 16 일 때 이프문 걸림)
걸린 후에 arr[i - 1] == 8 을 뺀 k의 값을 재귀로 돌림. 2뎁스로 들어간다
<2뎁스>
N == 2 라면
for문에서 i == 1 일때 (즉, arr[i] == 2 일때 이프문 걸린다)
걸린 후에 arr[i - 1] == 1 을 뺀 k 의 값을 재귀로 돌림. 3뎁스로 들어간다
<3뎁스>
1 이므로, 0을 리턴한다 -> 2뎁스로!
2.해당한는 값을 찾았으므로, 반전하면서 원래 길이 부분의 값을 도출하는 부분
<2뎁스>
재귀 recur() 로 리턴받은 값은 0이다. 따라서 1 - 0 의 값인 1 을 1뎁스로 리턴한다
<1뎁스>
재귀 reucr() 로 리턴받은 값은 1이다. 따라서 1 - 1 의 값인 0을 리턴한다. 답은 0
해당 과정을 값을 통해 보면
0110100110010110 --> 길이 16인 투에-모스 수열
10번째에 해당하는 녀석을 찾기 위해 -> 절반으로 가른 녀석의 2번째를 보자 (16->8 로 바꿔도 해당 녀석들은 대칭이므로). 그리고 나중에 "실제 값"은 반전되어 있을 것이므로, 한번의 반전이 필요하다 (반전횟수 ++ == 1)
2번째 녀석의 값을 보려면, 첫번째 녀석을 알아야 한다. 반으로 나눠서 (2->1) 값을 찾자. 반전이 필요하다 (반전횟수 == 2)
찾아온 녀석의 값은 0이다. 이제, 반전을 해주면서 실제 값을 찾아보자
0 -> 1 -> 0 ( 반전횟수 2)
따라서, 답은 0이다
