BOJ 2512 고등부 1번 예산
문제 링크 : https://www.acmicpc.net/problem/2512
문제 태그
파라매트릭 서치, 이분 탐색
문제 풀이
설정 할 수 있는 (가능한) 가장 큰 값을 묻는 문제이다. 이 부분을 보자마자 바로 파라메트릭 서치를 한 번 떠올려야 한다. 내가 어떤 값을 제사하여 그 값이 가능한가? 로 묻는 문제로 바꾸면 훨씬 더 쉽게 해결할 수 있을지에 대해 생각하면 파라메트릭을 쓸지에 대한 여부가 결정되고, 따라서 이 문제는 쓰는 것이 좋다. 더이상 말이 크게 필요없다. 지난번 글에서도 썻듯이 파라메트릭 서치 기본 문제이다.
코드
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
ll n, a[10000], m, lo, hi, ma, s;
int main() {
scanf("%lld", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
ma = max(a[i], ma);
s += a[i];
}
scanf("%lld", &m);
if (m >= s) {
printf("%lld\n", ma);
return 0;
}
lo = 0;
hi = 21000000000;
while (lo < hi) {
ll mid = (lo + hi) >> 1;
ll r = 0;
for (int i = 0; i < n; i++) {
if (mid >= a[i])
r += a[i];
else
r += mid;
}
if (r <= m)
lo = mid + 1;
else
hi = mid;
}
printf("%lld\n", lo - 1);
return 0;
}
BOJ 2517 고등부 2번 달리기
문제 링크 : https://www.acmicpc.net/problem/2517
문제 태그
문제 풀이
어떤 사람이 도달할 수 있는 최고 등수는 그 사람이 무조건 질 수 밖에 없는 사람의 수 +1 이다. 또한 그 사람수는 내 앞에 있는 사람들중 나보다 빠른 사람의 수이다. 따라서 갯수를 세는 2-elements 문제가 되고 그 수를 세는 것으로 풀 수 있다는 것을 알 수 있다.
나보다 앞에 있으면서도, 더 빠른 (실력수치가 더 높은) 사란의 수를 각각 세는 방법은 이 글을 읽으면 알 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
struct run{
long long int gap,gapid,whid;
};
bool sf1(run a,run b)
{
return a.gap>b.gap;
}
bool sf2(run a,run b)
{
return a.whid<b.whid;
}
run arr[500005];
long long int tree[1100005];
int n,m;
void update (int node,int start,int en,int index,long long int diff)
{
if(index<start || index>en) return;
tree[node] = tree[node]+diff;
if(start!=en)
{
update( node*2, start,(start+en)/2, index,diff);
update( node*2+1,(start+en)/2+1,en, index,diff);
}
}
long long sum(int node,int start,int en,int left,int right)
{
if(left>en||right<start) return 0;
if(left<=start && en<=right) return tree[node];
return sum(node*2,start,(start+en)/2,left,right)+
sum(node*2+1,(start+en)/2+1,en,left,right);
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&arr[i].gap);
arr[i].whid=i;
}
sort(arr+1,arr+n+1,sf1);
for(i=1;i<=n;i++)
arr[i].gapid=i;
sort(arr+1,arr+n+1,sf2);
int h=(int)ceil(log2(n))+1;
for(i=1;i<=n;i++)
{
update(1,1,n,arr[i].gapid,1);
printf("%lld\n", sum(1,1,n,1,arr[i].gapid) );
}
}
BOJ 2518 고등부 3번 회전 테이블
문제 링크 : https://www.acmicpc.net/problem/2518
문제 태그
DP
문제 풀이
이 문제를 조금만 관찰해보자. 테이블의 "상태"가 있을 것이고, 각 사람별로 어디까지 먹었는지의 "상태"가 있을 것이다. 그 중 최적의 상태로 이동하여 "최솟값"을 뽑는다. 사실 이정도 되면 그냥 문제를 읽는 과정에서 DP문제라는 느낌이 확 오게 된다.
테이블이 어떠한 상태들로 있을지를 생각해 봐야 한다. 조금 생각해보면 고려할 상태들은 최소 한 명은 자신이 그 차례에 먹고자 하는 음식이 앞에 있을 때라는 것을 알 수 있다. 이를 수치화, 경우화 시켜서 생각해보면
- 각사람이 i,j,k 번째 음식을 먹는 상태의 전 상태는 i-1,j,k번째 음식을 각각 먹었고, 이번에 1번사람이 i번째 음식을 먹음
- 각사람이 i,j,k 번째 음식을 먹는 상태의 전 상태는 i,j-1,k번째 음식을 각각 먹었고, 이번에 2번사람이 j번째 음식을 먹음
- 각사람이 i,j,k 번째 음식을 먹는 상태의 전 상태는 i,j,k-1번째 음식을 각각 먹었고, 이번에 3번사람이 k번째 음식을 먹음
따라서 dp[i][j][k][l]를 각 사람이 i,j,k 번째 음식까지 먹은 상태에서 현재 테이블이 1->i 에 맞춰져 있는지, 2->j에 맞춰져 있는지, 3->k에 맞춰져 있는지를 l에 값으로 저장해 놓은 상태에서 그 상태에 도달하기까지 돌린 판의 최소 횟수라고 한다. 그러면 dp[i][j][k][l]은 3개의 상태에서 올 수 있고 그 차이의 값은 O(1)만에 구할 수 있기 때문에 전체 시간 복잡도 $O(pi^3)$ 에 풀 수 있다.
코드
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll arr[1010101];
ll brr[1010101];
ll crr[1010101];
ll dp[101][101][101][4];
int main(){
ll i,j,k,l,m,n;
scanf("%lld",&n);
ll a1,a2,a3;
scanf("%lld",&a1);
for(i=1;i<=a1;i++){
scanf("%lld",&arr[i]);
arr[i]--;
}
scanf("%lld",&a2);
for(i=1;i<=a2;i++){
scanf("%lld",&brr[i]);
brr[i]--;
brr[i]=(brr[i]-n/3+n)%n;
}
scanf("%lld",&a3);
for(i=1;i<=a3;i++){
scanf("%lld",&crr[i]);
crr[i]--;
crr[i]=(crr[i]+n/3)%n;
}
for(i=0;i<=a1;i++)
for(j=0;j<=a2;j++)
for(k=0;k<=a3;k++)
for(l=1;l<=3;l++)
dp[i][j][k][l]=1e18;
dp[0][0][0][1]=0;
dp[0][0][0][2]=0;
dp[0][0][0][3]=0;
arr[0]=brr[0]=crr[0]=0;
for(i=0;i<=a1;i++)
for(j=0;j<=a2;j++)
for(k=0;k<=a3;k++){
if(i){
dp[i][j][k][1]=min(dp[i][j][k][1],dp[i-1][j][k][1]+min((n+arr[i-1]-arr[i])%n,(n+arr[i]-arr[i-1])%n));
dp[i][j][k][1]=min(dp[i][j][k][1],dp[i-1][j][k][2]+min((n+brr[j]-arr[i])%n,(n+arr[i]-brr[j])%n));
dp[i][j][k][1]=min(dp[i][j][k][1],dp[i-1][j][k][3]+min((n+crr[k]-arr[i])%n,(n+arr[i]-crr[k])%n));
}
if(j){
dp[i][j][k][2]=min(dp[i][j][k][2],dp[i][j-1][k][1]+min((n+arr[i]-brr[j])%n,(n+brr[j]-arr[i])%n));
dp[i][j][k][2]=min(dp[i][j][k][2],dp[i][j-1][k][2]+min((n+brr[j-1]-brr[j])%n,(n+brr[j]-brr[j-1])%n));
dp[i][j][k][2]=min(dp[i][j][k][2],dp[i][j-1][k][3]+min((n+crr[k]-brr[j])%n,(n+brr[j]-crr[k])%n));
}
if(k){
dp[i][j][k][3]=min(dp[i][j][k][3],dp[i][j][k-1][1]+min((n+arr[i]-crr[k])%n,(n+crr[k]-arr[i])%n));
dp[i][j][k][3]=min(dp[i][j][k][3],dp[i][j][k-1][2]+min((n+brr[j]-crr[k])%n,(n+crr[k]-brr[j])%n));
dp[i][j][k][3]=min(dp[i][j][k][3],dp[i][j][k-1][3]+min((n+crr[k-1]-crr[k])%n,(n+crr[k]-crr[k-1])%n));
}
}
printf("%lld\n",min({dp[a1][a2][a3][1],dp[a1][a2][a3][2],dp[a1][a2][a3][3]}));
}BOJ 2519 고등부 4번 막대기
문제 링크 : https://www.acmicpc.net/problem/2519
문제 태그
문제 풀이
일단 우리가 원하는 최종상태를 생각해보자. 어떤 두 막대기도 겹쳐있으면 안된다. 이 말을 바꿔서 생각하면 겹쳐있는 막대기의 쌍은 없어야 한다. 이 말을 다시 생각해보면 처음 상태에서 겹쳐있는 두 막대기중 적어도 하나는 제거를 해야한다. 이 말을 생각해보면 2-SAT이 떠오른다. 모든 쌍에 대해서 둘 중 하나는 제거를 해야한다. 이 말을 좀 더 생각해 보면 둘 중 하나를 제거 안했으면 (not p이면) 나머지 하나는 제거를 해야한다 (q이다) 그러면서 한 사람이 자신의 막대기는 하나만 제거할 수 있기 때문에 자신의 막대기중 하나를 제거했으면 (p이면) 다른 막대기는 제거하지 못한다. (not q이다)
선분교차 알고리즘을 활용하여 모든 쌍에 대해서 두 선분이 교차하는 지 확인하자. 만약 교차한다면 위와 같은 조건을 추가할 수 있을 것이다. 또한 한사람당 최대 한개만 뺄 수 있다는 조건도 위와 같이 변형하여 문제를 아예 2-SAT으로 바꿔 버릴 수 있다. 따라서 나머지 부분은 그냥 2-SAT 문제를 해결하는 방식을 그대로 따라서 진행하면 된다.
코드
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
struct poi{
ll x,y;
bool operator <(const poi &t) const {
if(x==t.x) return y<t.y;
return x<t.x;
}
};
ll ccw(poi a,poi m,poi b)
{
ll t=(a.x-m.x)*(b.y-m.y)-(a.y-m.y)*(b.x-m.x);
return (t<0)-(t>0);
}
struct lin{
poi f,s;
};
bool cross(lin a,lin b)
{
if(ccw(a.f,a.s,b.f)*ccw(a.f,a.s,b.s)==0&&ccw(b.f,b.s,a.f)*ccw(b.f,b.s,a.s)==0)
return !(max(a.f, a.s)<min(b.f,b.s)||max(b.f, b.s)<min(a.f,a.s));
return ccw(a.f,a.s,b.f)*ccw(a.f,a.s,b.s)<=0&&ccw(b.f,b.s, a.f)*ccw(b.f,b.s,a.s)<=0;
}
lin arr[30300];
vector<ll> v[30300];
vector<ll> rev[30300];
ll vis[30300];
vector<ll> scc[39309];
ll num[30030];
stack<ll> st;
ll gp;
void dfs(ll x){
vis[x]=1;
for(auto k:v[x]){
if(vis[k]) continue;
dfs(k);
}
st.push(x);
}
void dfs2(ll x){
vis[x]=1;
scc[gp].pb(x);
num[x]=gp;
for(auto k:rev[x]){
if(vis[k]) continue;
dfs2(k);
}
}
ll mod;
ll ch(ll x){
return mod-x;
}
vector<ll> ans;
int main(){
ll i,j,k,l,m,n,nn,nnn;
scanf("%d",&n);
nn=3*n;
nnn=2*nn;
mod=nnn-1;
for(i=0;i<nn;i++){
scanf("%d %d %d %d",&arr[i].f.x,&arr[i].f.y,&arr[i].s.x,&arr[i].s.y);
}
for(i=0; i<n; i++){
v[3*i].pb(ch(3*i+1));
v[3*i].pb(ch(3*i+2));
v[3*i+1].pb(ch(3*i));
v[3*i+1].pb(ch(3*i+2));
v[3*i+2].pb(ch(3*i));
v[3*i+2].pb(ch(3*i+1));
rev[ch(3*i)].pb(3*i+1);
rev[ch(3*i)].pb(3*i+2);
rev[ch(3*i+1)].pb(3*i);
rev[ch(3*i+1)].pb(3*i+2);
rev[ch(3*i+2)].pb(3*i);
rev[ch(3*i+2)].pb(3*i+1);
}
for(i=0;i<nn;i++)
for(j=i+1;j<nn;j++)
if(cross(arr[i],arr[j])){
v[ch(i)].pb(j);
v[ch(j)].pb(i);
rev[i].pb(ch(j));
rev[j].pb(ch(i));
}
for(i=0;i<nnn;i++)
if(!vis[i])
dfs(i);
for(i=0;i<nnn;i++)
vis[i]=0;
while(!st.empty()){
ll x=st.top();
st.pop();
if(vis[x]) continue;
gp++;
dfs2(x);
}
for(i=0;i<nn;i++){
if(num[i]==num[mod-i]){
printf("-1");
return 0;
}
if(num[i]>num[mod-i]) ans.pb(i+1);
}
printf("%d\n",ans.size());
for(auto x:ans)
printf("%d ",x);
}'코딩 > 백준 문제 풀이' 카테고리의 다른 글
| BOJ 13548 - 수열과 쿼리 6 (1) | 2020.06.04 |
|---|---|
| BOJ 13547 - 수열과 쿼리 5 (1) | 2020.06.04 |
| BOJ 13546 - 수열과 쿼리 4 (0) | 2020.05.27 |
| BOJ 13554 - 수열과 쿼리 9 (0) | 2020.05.26 |
| BOJ 14435 - 놀이기구 2 (0) | 2020.05.24 |