Pizza( Atcoder 238-B )

문제 : https://atcoder.jp/contests/abc238/tasks/abc238_b

B - Pizza

 

문제 파악하기

pizza를 주어진 각도만큼 회전시키고 잘랐을 때, 가장 큰 피자의 각도를 구하는 문제입니다. 피자의 각도는 0˚ ~ 359˚까지 있으며, 동일한 위치를 다시 자르지 않는다는 점을 고려하면 문제를 해결할 수 있습니다.

 

문제 해결하기

동일한 위치를 다시 자르지 않기에 우리는 0˚ ~ 359˚까지 배열을 사용해서 잘린 적이 있는지 확인하면 됩니다. 다만, 입력되는 각도는 360˚를 넘을 수 있기 때문에 나머지 연산자를 적절하게 사용하면 됩니다. 자르는 과정이 종료되었다면 잘린 각도 사이의 값 중 최댓값을 구하면 문제를 해결할 수 있습니다. 다만, 가장 처음 0˚를 자른다는 걸 유념하세요.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 360
using namespace std;
 
int N, a;
vector< int > pizza;
 
int cur, vmax;
 
int main() {
    scanf("%d", &N);
 
    pizza.push_back(0);
    for(int i=1;i<=N;i++) {
        scanf("%d", &a);
        cur = (cur + a)%360;
 
        pizza.push_back(cur);
    }
 
    sort(pizza.begin(), pizza.end());
 
    vmax = (360 +pizza[0]) - pizza.back();
    for(int i=1;i<pizza.size();i++) vmax = max( vmax, pizza[i]-pizza[i-1] );
 
    printf("%d", vmax);
}

후기

추상화 과정이 필요한 문제입니다. 최근 풀었던 앳코더 B번 중 가장 재미있는 문제라고 생각합니다. 배열을 배운 사람들에게 추천하고 싶은 문제입니다. 케익 자르기(https://codeup.kr/problem.php?id=2628)의 상위 호환 문제라고 생각합니다.