[수학] 직관적으로 안와닿는 수학문제 (BOJ 1188 음식 평론가)

문제에서 더 이상의 구체적인 조건 없이 단순히 자르는 행위만을 요구하는걸로 봐선,

특별한 기교 없이 아이디어로 푸는 문제임을 파악했다.

 

이후 직접 테스트 케이스들 만들어가며 규칙을 찾아보려고 했다.

주어진 두 수를 서로 나눠보며, 나눈 결과값이 어떤 의미를 가지는지 생각해보았다.

 

유클리드 호제법은 본래 최대 공약수를 찾는 문제지만, 이 문제가 최대 공약수 관련 문제라는 느낌은 받지 못했다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int ans = 0;

// 나누어 떨어질 때 까지 반복해서 나눔;
// 원래는 최대공약수 찾는 방법이지만 여기선 그 용도로 사용되지 않음.
// f : true시 자름, false일때 안자름
void Euclidean(int a, int b, bool f){
    if(a%b){
        Euclidean(b, a%b, !f);
        if(f)
            ans += b*(a/b);
    }
    else{
        if(f)
            ans += b*(a/b-1);
        return;
    }
}

int main(void) {
    int M, N, tmp;
    cin >> N >> M;

    Euclidean(M,N,true);
    cout << ans;
}

---

다른 사람들의 풀이를 보면, m - gcd(m,n) 라는 결론에 도달하더라.

사람과 소시지의 최대공약수를 응용한 문제다.
만일 소시지가 4개, 사람이 6명이라면 결국에는 소시지 2개를 사람 3명이서 나눠야 된다고 생각할 수 있다.
4개/6명에서 2개/3명으로 줄이는 과정은 최대공약수로 나눴다는 점이다.
2개와 3명은 더이상 나눌 수 없기 때문에, 3명이서 나누기 위해서는 소시지를 (3-1)번 조각 내어야만 한다.

 

이를 수식으로 작성하면 result = gcd * (m/gcd - 1) = m - gcd가 된다

출저 : noel-embedded.tistory.com/792

다른 예시로, 소시지 15개를 5명이서 나누는 경우를 생각해보자.

직관적으로, 3개를 1명이 나누는 답에 5배를 해주면 같지 않을까?

여기서 5는 5와 15의 최대공약수고.

 

20개를 6명이서 나누는 경우도 생각해보자.

이 경우 최대 공약수로 두 수를 나눠주면 : 10개를 3명이서 나누는 경우가 된다.

10개를 3명이서 나누려면, 10/3 = 3개씩 일단 안자르고 나눠준 다음, 남은 10%3 = 1개를 3명이서 잘라 나누면 된다.

이때 (3-1)번 자르겠지.

 

마지막 케이스를 살펴보자. 22개를 6명이서 나누는 경우.

11개를 3명이서 나눈다고 생각할 수 있고, 3명이서 3개씩 안자르고 나눈 후에, 남은 2개를 3명이서 잘라 나눈다.

이때도 (3-1)번만 자르면 된다. 

 

결론적으로, 평론가들끼리 다 나누고 최종적으로 남는 소시지 개수 X는 0<=X<m/gcd

X==0 일때는 평론가들끼리 소시지를 딱 나누어 떨어지게 가져가는 경우라 안잘라도 됨.

0<X<m/gcd 일때는 m/gcd-1번 자르는 경우의 수 밖에 없다.

 

 

직관적으로 쉽게 와닿지 않아서 힘든 문제였음.