백준 14445 케이크(?) 자르기 C++

해설

애드혹 문제라서 발상을 떠올리는게 쉽지 않았다.

케이크의 높이가 명시되어 있지 않으므로, 케이크의 높이가 케이크 윗면의 가로 길이랑 다를 수 있음을 인지해야 한다.

 

케이크의 높이가 다르기에 자르는 방식에 따라 케이크의 옆면에 묻은 생크림이 달라질 수 있다.

이에 따라, 케이크의 윗면과 옆면을 어떻게 배분해야 하는가에서 난관이 생긴다. 그러나 이는 원을 n등분 할 때를 떠올리면 해결된다.

 

 

윗면이 원인 원통형 기둥을 생각해보자. 원의 중심을 따라 n등분하면 옆면을 쉽게 배분할 수 있다.

 

그래서 이 문제에서는 모든 절취선이 정사각형의 중심을 통해서 n등분이 되면 높이, 즉 옆면을 신경쓰지 않고 케이크를 수직으로 자르면 된다.

 

이제, 케이크의 윗면만 n등분해서 배분하면 되는 문제로 바뀐다.

 

n = 1의 경우, 케이크를 안잘라도 되니까 답은 0이다.

 

n이 홀수인 경우, 하나의 조각을 나누어주다가, 나머지 한명에게는 나누어진 2 조각을 합쳐서 준다.

 

n이 짝수인 경우, 조각의 정사각형의 변(정사각형 케이크의 자르기 전 모서리)에 해당되는 길이의 합이 모두 같도록 자른다.

 

그래서 n이 홀수인 경우와 짝수인 경우로 구분할 수 있는데, 이는 작도를 하면서 짝수는 n/2로, 홀수는 n/2+1로 그릴 수 있음을 알 수 있다.

 

 

간단하게 작도한 그림

답

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll n;
    cin>>n;
    if(n==1) cout<<0;
    else if(n&(1<<0)) cout<<(n/2)+1;
    else cout<<n/2;
}

출처

5등분은 스스로 찾아내었으나 6등분은 감이 왔는데도 그림이 제대로 안그려져서 대체...

 

3등분

https://x.com/hyalillot/status/1407358265457922048

 

6등분

10. 정사각형 케이크는 어떻게 똑같이 나눌까?