Red Salmon

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

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

예전부터 풀어야지 하며 안풀었던 문제를 드디어 풀었다. 엄청 간단할줄 알았는데 생각외로 해맸다. 졸려서 그런거 같다.

이 문제는 이름만 봐도 스택을 써야할듯한 문제이다. 내용도 스택을 쓰세요~~ 라고 말하는것 같다. 하지만 경험상 스택문제의 경우 거의 대다수는 스택이 필요없고 배열로만 할 수 있으며, 훨씬 속도면에서 빠르다. 구현도 훨씬 쉽다. 그러나 큐나 리스트같은경우는 배열로는 답이 나오지 않는 경우가 대다수이다.

이 문제에 먼저 기억해야할 점은 불가능한경우 NO를 출력하라고 한 점이다. 불가능할 경우가 있다는 말이니 예외처리를 해줘야한다. 나는 역시 이부분을 놓쳤다가 나중에서야 다시봤다. 하지만 이번엔 빨리 캐치해냈다.

풀이를 살펴보면 다음과 같다.

1. 입력을 받아 스택의 최상단 값과 비교를 한다.

2. 입력값이 최상단 값보다 크다면 현재 사용된 가장 큰 수부터 입력값까지 스택에 새로이 쌓는다.

3. 그 후에 최상단 값과 입력값을 비교한다.

4. 일치하면 최상단 스택을 지워버리고, 일치하지 않는다면 불가능한 경우다.

여기서 설명을 덧붙이자면 스택에는 현재 숫자의 입력에 따라 순차적으로 쌓여있다. 그런데 입력값이 스택의 최상단 값과 일치하지 않는다는 말은 스택의 순서를 무시한 경우이거나, 이미 사용된 수이거나, 전혀 관련없는 수일가능성이 높다. 그렇기 때문에 불가능한 경우가 된다. 이해가 되지 않는다면 역시 손으로 써보면서 증명해보는게 최고다. 그리 어렵지 않은 문제였다.

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

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

이 문제는 굉장히 쉽다. 그러나 나의 고질적인 문제인 대충읽기로 인해 굉장히 해맸다. 그래서 기록해야겠다고 생각했다.

 먼저 문제는 입력의 쌍이 들어오고, 여기서 덩치순위를 정하는 것이다. 나는 문제를 대충읽고, 정렬이 답이라 생각했다.

stable_sort를 통해 정렬을 시키고 바로 다음 인덱스와 크기를 비교하여 다르면 rank를 갱신하고 둘중 하나만 같으면 rank를 그대로 가는 방식으로 값을 매겼다. 물론 pos라는 값을 카운팅해주며 rank가 변할때 앞에 몇사람이 있었는지 체크하였다. 

그런데..오답을 맞았다. 직감적으로 이건 또 내가 문제를 잘못읽었겠구나 생각하며 천천히 정독하였다.  역시나..

문제에서 등급을 매기는 방법은 

 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다.

이라고 한다. 즉 정렬도 필요없고 입력받은 사람들의 데이터들을 쭉 찾으면서 자기보다 큰사람이 몇사람이나 있는지를 체크하는 것이었다. 매우 간단했다....

이런문제에 40분가량을 소요한것이 매우 우둔하며 후회스럽다. 과거 이런 습관으로 인해 큰시험에서떨어졌으면서 바뀌지 않는걸 보니 이 문제를 자각하지 못하고 있는것 같다. 쉽더라도 집중해야 한다는걸 기억하기 위해 풀이를 적었다.

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

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

이 문제는 가볍게 보면 정수 a, b, c 3개를 입력 받는다. 그리고 pow(a, b)%c를 하면 끝이다. 하지만 이렇게 쉬운문제는 풀지도 않는다. 이 문제의 요건을 보면 a, b, c전부 INT_MAX의 인풋을 받는다.

즉 최악의 경우 pow(INT_MAX, INT_MAX)의 경우가 발생한다. 당연히 이런 문제는 머리를 쓰라는 것이다.

전에 공부하면서 math.h에 담겨있는 pow함수는 단순 반복문으로 만든 함수가 아니라는걸 알았다.(확연한 속도차이)

그래서 과연 stl의 pow는 어떻게 구현이 되있나 생각해봤다. 맞는지 아닌지는 모르겠으나 내가 생각한 방법도 상당한 속도를 가진다. 

예제를 살펴보면 10 11 12 가 인풋으로 들어오고 이는 pow(10, 11)%12이다.

그런데 10^2는 100이고 100^2 는 10000인데 이는 10^4이다. 그리고 10000에 다시 제곱을 하면 결국 10^8이 된다. 

이렇게 3번만에 10^8까지 구하였다. 10씩 8번 곱하는 경우보다 훨씬 계산이 줄었다.

그리고 현재 2의 제곱씩 경우의 수를 늘려가고 있기 2^3인 8을 현재 b에서 뺀다.

남은 3은 다시 위과정을 반복한다. 

이렇게하면 매우 적은 연산으로 값을 추출할수있다.

그리고 이문제에서 주목해야할 점은 long long이어도 20억이상의 수를 곱하다보면 값이 넘어서버릴가능성이 있다. 

여기서 (a+b) mod c = (a mod c + b mod c) mod c 식을 응용하여 계속 값을 줄여준다.

그러면 답이 나온다. 이 설명이 이해가 되지 않는다면 인풋을 2 6 100 이런식으로 해서 계산해보면 이해가 될것이다.

출처 : 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)께 감사드립니다.