BOJ 2118, 두 개의 탑
ProblemSolving ·이 문제는 완전탐색 문제라고 생각합니다.
풀이
범위가 5만이라 이중포문이면 25억 대략 2.5초를 생각해서 주춤했었지만 j가 1부터 갈 필요가 없기때문에 사용할 수 있었습니다.
총 거리의 합을 sum 배열에 저장해주고 i는 첫번째 성을 기준으로 잡고 하나씩 arr[j]의 값을 빼주면서 거리를 알아냈습니다.
시계방향의 경로와 반시계방향의 경로를 값은 각각 ans 와 sum-ans 가 되겠죠? 비교해서 최대값을 Max 값에 저장해줬습니다.
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<map>
using namespace std;
int n,sum, arr[50001],ans, Max;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &arr[i]);
sum += arr[i];
}
for (int i = 1; i <= n - 1; i++)
{
ans = sum;
for (int j = i + 1; j <= n; j++)
{
ans -= arr[j];
Max = max(Max,min(ans, sum-ans));
}
}
printf("%d", Max);
return 0;
}