Red Salmon

출처 : https://www.acmicpc.net/problem/9471

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/9471.cpp

이건 진짜 피사노주기이다. 바로 전에 풀었던 문제의 원형이라고 볼 수 있다. 우선 이문제에 여러가지 규칙이 있지만 이문제를 풀때는 저 규칙과 전~~~~~혀 상관이 없다. 필자는 저 규칙이 있으니 뭔가 있나? 혹시 DP인가? 싶었지만 아니었다.

피사노주기는 아무리 찾아봐도 외국자료들 뿐이 없었다. 먼저 전에 풀었던 문제는 피사노주기값을 구하기가 굉장히 쉬웠고 그를 통해 값을 구할 수 있었다. 그런데 만약, 정의된 규칙이 통하지 않는 문제라면 어떻게 될까? 

즉 명시된 규칙들

• m > 2인 경우에 k(m)은 짝수이다.
• 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
• k(m) ≤ m2 - 1
• k(2n) = 3×2(n-1)
• k(5n) = 4×5n
• k(2×5n) = 6n
• n > 2라면, k(10n) = 15×10(n-1)

이 적용되지 않는 경우라면 어떻게 풀어야 하는가? 정말 난감했다. 위키피디아를 검색해보니 대략 이런 연산이 가능하다고 한다.

피사노 주기

출처:https://en.wikipedia.org/wiki/Pisano_period

위의 피사노 주기를 살펴보면 전혀 규칙성이 없다. 그런데 피사노주기 12번째 값을 구하는 예시가 있다. 

12=3*4이다. 여기서 3번재 피사노값과 4번째 피사노값의 최소공배수를 구한다. 그럼 lcm(8, 6)=24가 된다. 실제로 12번째 피사노값은 24이다. 더 응용해보니 12=2*6일때 lcm(3, 24) 이므로 최소공배수는 24이다. 10인 경우는 10=2*5 이므로 lcm(3, 20)=60이 된다. 오!!! 성립하는것 같다!! 하지만...

만약 소수라면? 단적으로 7을 구하는 방법이나, 11을 구하는 방법이 존재하지 않는다. 여기에 다시 위키는 수식을 주었다.

  For prime numbers p, these can be analyzed by using Binet's formula:

 where  is the kth metallic mean

대략 저 수식을 이용하라는것 같은데..k 가 뭐지..? 하며 이것저것 찾아읽었다. 자세한건 직접 저 위의 위키 링크를 가서 숫자이론쪽을 살펴보면 된다. 저기에대략적으로 k값을 정하는 방법 이런게 나오지만, 별의미 없어보이고 너무 어려운 알고리즘은 틀린 알고리즘일 가능성이 농후하다. 

그리고 찾아보니 공통된 알고리즘이 있어 나도 공부해보았다.

        m1 = m2 = 1;
        period = 0;
        do
        {
            int temp = m1;
            m1 = m2;
            m2 = (temp+m2) % m;
            period++;
        } while (!(m1 == 1 && m2 == 1));

살펴보면 m1과 m2가 있는데 이것을 1로 초기화하였다. 피보나치는 2개의 수를 가지고 다음 수를 정하는 것이다. 피보나치의 1번째 2번째는 1이라는 사실을 우리는 알고있다. 

그리고 7번째 줄은 (a + b) mod c = (a mod c + b mod c) mod c

이공식을 이용한 것이라고 한다.  결국 우리는 이전 2개의 수의 합이 현재 피보나치이고 이걸 m으로 나누는 값을 추출하여 주기를 만든다는것을 알고 있으니, 위의 공식을 사용 할 수 있겠다.

여기서 a mod c 는 m1이 되고 b mod c는 m2가 된다. 처음에는 이전 2개의 수를 더하고 m으로 나눈다. 이수는 자동적으로
A mod B가 되기때문에 이제 주기가 계속 나온다. 여기서 다시 처음의 1, 1이 나온다면 주기가 완성이 되었다는 말이니 종료를 하면 되고, 그동안 period가 카운팅되어 이만큼의 주기라는걸 알수있다.

이해하기 힘든 문제였다.

P.S.

이해에 도움을 주신 백준의 두 유저분(cubelover, mendou12)께 감사드립니다. 

출처 : https://www.acmicpc.net/problem/2749

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2749.cpp

오늘 정확히는 어제 공부한 내용은 피사노주기이다. 2일이나 공부했는데 이해가 쉽게 가지 않았다.

먼저 문제는 피보나치수를 구하는데 10^18이 최대 인풋이다. 단순 포문으로는 절대 답을 구하지 못한다.
(그 전에 공부한 최소값문제도 단순 탐색으로는 구하지 못하는 문제였다.)

많은 고민을 해보다가 도무지 해결책이 떠오르지 않아, 검색을 하였다. 그리고 알게된 것이 피사노주기(pisano period)이다.

바로 다음문제(9471)에 피사노 주기에 대한 설명이 있기에, 설명은 스킵하고 문제의 해결법을 적겠다.

먼저 피보나치에서 변하지않는 진리가 있다면 이전 2개의 수를 가지고 현재 값이 나온다는 것이다. 그리고 현재 문제는 1,000,000으로 나눈 값을 출력하라고 하였다. 이게 포인트인것이다.

피사노주기의 규칙에 의하면 피보나치수를 m으로 나누면 반드시 주기가 생긴다고 한다. 주기가 있다면 수들은 반복이 된다.

즉, 주기만 찾는다면 불필요한 연산을 전부 제외하고 딱 그만큼만 계산하면 된다.

이문제에서 m은 1,000,000이라고 하였으니  피사노 주기 규칙에 의해 n > 2라면, k(10n) = 15×10(n-1)이 성립하게 된다.

그럼 1,000,000은 10^6이므로 15*10^(6-1) 이므로 1500000이 된다. 이렇게 간단하게 주기를 찾았다. 이제 주기로 나눠주기만 하면 된다. 그래서 포문을

for (int i = 1; i < n%pisano; i++)

이렇게 표현하였는데 입력된 n값에 피사노주기로 나눠주고 그만큼만 탐색을하면 간단히 해결이 된다. pisano값이 150만 이니 모든 계산은 최대 150만 이내로 해결이 될 것이다. 

솔직히.. 피사노 주기를 모른다면 어떻게 풀지..?(물론 푼사람도 있었다... 대단합니다.)

출처 : https://www.acmicpc.net/problem/10868

해답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/10868.cpp

위 문제는 n만큼 입력을 받고 m개의 구간을 입력받아 그 구간내에서 최소값을 출력하는 문제이다. 

입력에서 구간이 입력되는데 이 구간은 앞수가 작고 뒷수가 크다. 역으로 입력이 들어오진 않는다.

언뜻보면 굉장히 쉽지만 쉬운 문제는 아니다. 단순히 생각만 한다고 풀 수 있는 문제는 아니다.

먼저 이문제를 정확히 이해하기 위해서는 시간복잡도를 계산해 봐야한다. 우선 입력은 어떻게 하지 못하므로 O(N)이 있고 계산시에는 특정 구간이지만 최악의 경우 시작값이 1이고 끝값이 N일수도 있다. 그럼 M이 100,000이 최대라고할때 O(100,000*100,000) 이 된다. 그러므로 당연히 단순 탐색으로는 TL을 피할 수 없다.

이 문제의 풀이방법은 여러가지가 있겠지만, 나는 세그먼트 트리(Segment Tree)로 풀었다. 세그먼트 트리로 풀게 되면 딱히 알고리즘이 있는게 아니고 그냥 그 자체가 된다. 그렇기에 세그먼트 트리란 무엇인지 정리해보겠다.

필자는 https://www.acmicpc.net/blog/view/9#comment-42 여기서 공부하였으며, 내가 이해한바를 다시 정리해보겠다.

우선 세그먼트 트리는 배열안의 특정 구간의 어떤 값을 찾을때 아주 용이하다 이 알고리즘의 시간복잡도는 O(logN)이다.

트리가 다음과 같이 구성되어 있다고 가정하자. 물론 입력에서 n은 2의 제곱수가 아닐 경우는 아주 많을 것이다. 그러나 개념만 이해하면 된다. 우선 n이 8이고 배열 값으로 1부터 8까지 입력을 받았다고 가정하자. 세그먼트 트리의 상위 값으로는 왼쪽 오른쪽 값을 비교하여 문제가 원하는 최소값을 넣는다. 그럼 아마 이런식으로 구성이 될 것이다.

위로 올라가면 두 수를 비교하여 작은 값을 놓고 다시 위로 올라가고 다시 작은 값을 놓고 이런식으로 할 것이다. 하지만 문제에서는 4 7을 입력할수 있다. 그럼 구간 4부터 7까지를 비교해야 하는데 다음과 같은 노드가 체크가 될 것이다.

그럼 저 3가지를 비교하면 최소값을 찾을 수 있다. 이런식으로 비교하면 모든 구간에 대해 최소값을 찾을 수 있다. 바로 소스부터 살펴보겠다.

int init(vector &arr, vector &tree, int node, int start, int end)
{
	if (start == end) 
		return tree[node] = arr[start];
	else 
		return tree[node] = min(init(arr, tree, node * 2, start, (start + end) / 2), 
								init(arr, tree, node * 2 + 1, (start + end) / 2 + 1, end));
}
//초기화 부분이다

먼저 인자를 살펴보면 처음은 입력받은 배열이 되고, 두번째는 값이 담길트리이다. 트리는 당연히 원래 배열보다 커야한다. 위만 보더라도 8개의 입력배열이 있지만 트리는 (2^4)-1개의 노드를 가지고 있으므로 그만큼의 배열이 되야한다. 계산해보면 대략적으로 3배 미만으로 가지고 있다. 필자는 최대인풋이 10만이므로 트리는 30만개를 가지도록 하였다.

그리고 들어오는 노드는 시작 노드이다. 당연히 시작노드는 1번노드가 되는것이고 시작값은 구간을 의미하고 start와 end는 그 노드가 가지고있는 구간을 의미 한다 즉 1~2, 1~4 등을 의미한다. 그 구간내에서 가장 작은 값을 찾으라는 것이다. 밑 부분에  node*2, node*2+1은 트리의 기본개념을 보면 이해가 가능할것이다. 왼쪽 노드와 오른쪽 노드의 순서 배치를 어떻게 하는지 모른다면 지금 바로 트리의 기본을 다시 공부해야한다.

if문으로 구분한 것은 start==end인경우는 현재 node값이 끝에 도달하여 더이상 왼쪽과 오른쪽이 없다고 생각하면 된다. 그렇기에 값을 주는것이고 그외의 경우는 계속 왼쪽과 오른쪽을 뻗어나가도록 한다.

int MIN(vector &tree, int node, int start, int end, int left, int right)
{
	if (left > end || right < start) 
		return MAX;
	if (left <= start && end <= right)
		return tree[node];

	return min(MIN(tree, node * 2, start, (start + end) / 2, left, right), 
				MIN(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right));
}
//최소값을 찾는 부분이다

이 부분의 인자를 살펴보면 트리를 넘겨주고 node번호와 이번엔 left, right가 주어지는데 실제 입력에서 구간을 의미 한다. 그리고 해당 구간내에서 최소 값을 계속 찾아간다. min()은 algorithm 헤더에 있으며 구현도 쉽기 때문에 설명을 생략한다.

처음 if (left > end || right < start)이 부분은 node가 담당하는 부분과 찾고자하는 구간이 전혀 겹치지 않을 경우이다. 이때는 찾을 수 없는 경우이므로, MAX값을 리턴해준다. 필자는 MAX를 21억으로 설정했는데, 문제 설명에서 입력값의 최대는 10억이라고 하였기 때문이다. 10억보다 큰 수면 된다.

그리고 두번째 if (left <= start && end <= right)는 노드의 구간값이 찾고자 하는 범위내에 완전히 포함되었다면 그 밑으로는 갈 필요가 없기 때문에 해당 노드의 값을 리턴해준다. 그리고 그 외의 경우는 계속 왼쪽 오른쪽으로 찾으면서 최소값을 찾는다.

쉽지는 않았던 문제이며, 혼자서 완전히 코딩하려면 많은 연습이 필요할 듯 싶다.

출처 : https://www.acmicpc.net/problem/2505 (정확히는 정보올림피아드 문제이다.)

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2505.cpp

이 문제의 경우 정말 어렵지 않다. 다만 처음에 이렇게 생각하기가 참 힘들다. 이래서 알고리즘을 공부하나보다. 정말 역발상으로 하면 풀리는 문제였다.

우선 이 문제에 먼저 집중해야할 부분은 스페셜 저지라는 점이다. 답은 여러개라는 말이다. 

문제를 보면 입력이 주어지는데 이 입력된 수들은 2번 뒤집혔다는 말이다. 문제가 이해가 되지 않는다면 다시 읽어보면 된다.
알고리즘 공부를 한다면 문제 이해는 기본중의 기본이다. 문제가 정말 잘못되어 이해하지 못한경우라면 정답자도 없을 것이다.

암튼 나의 알고리즘은 이렇다.

1. 1 혹은 n값의 위치는 정해져있다. 즉 맨앞이거나 맨 뒤이다. 우선 여기에 초점을 맞춘다.

2. 처음엔 1을 먼저 앞으로 빼본다. 그리고 변경된 수들에서 다음 수인 2를 찾는다.

3. 2가 원래 위치와 맞는 숫자라면 다시 다음수인 3을 찾고, 틀리다면 2를 찾아서 다시 뒤집어 본다.

4. 두번 뒤집어도 값이 나오지 않으면 이번엔 맨 처음 수들에서 n값으로 찾아본다.

5. 위 과정을 다시 반복하다보면 둘중 하나에서는 반드시 정답이 나온다.

고등학생문제보니 3번 뒤집기가 있다. 이건 다르게 생각해봐야할 것 같다. 아직 풀지는 않았지만, 이 문제와는 아주 다른 해결책이 있을것이다.

정보올림피아드는 이런 방법을 허용하지 않고, 보통 비슷한 문제를 전혀다른 해결책으로 풀게 한다. 하지만 1과 n값의 위치가 포인트일것이다. 

굳이 이 수들이 앞에 있는데 뒤로 보냈다가 다시 앞으로 보내는 번거로움은 하지 않을것 같다.