딥3이다. 쉬운 문제들만 있기 때문에 연습하기에 좋다.
또 뭔 문제를 풀지 모를 때 문제를 알아서 던져줘서 좋기도 하다.
민트 이하한테는 떡상의 기회도 되는데, 나는 민트가 아니니까 해당사항이 없다.
A번이니만큼 간단한 문제다.
일단 N=1이면 답이 0이고 N=2일 때 답이 m인 것은 매우 자명하다.
N>=3일 때는 답은 m*2이다. 직관적으로 보일 수 있지만 증명해보자.
0 m 0 0... 꼴로 답이 m*2이게 할 수 있다. 그럼 답이 m*2를 초과할 수 없음을 증명한다.
답을 c1*a1+c2*a2+c3*a3+c4*a4+...+cn*an 꼴로 나타낼 수 있다. 이때 -2<=ci<=2임이 자명하다. ci에 영향을 끼칠 수 있는 항은 |a[i-1]-a[i]|과 |a[i]-a[i+1]| 뿐이기 때문이다.
그러면 식을 -2*(a1+a2+a3+...+an)+((c1+2)*a1+(c2+2)*a2+...+(cn+2)*an) 꼴로 나타낸다. -2*(a1+a2+..+an)=-2m이다. ((c1+2)*a1+(c2+2)*a2+...+(cn+2)*an)<=4*a1+4*a2+4*a3+4*a4+...+4*an=4*m이다. 그럼 두 개를 더한 것은 -2*m 이상 2*m 이하로 2*m 이하이다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int tc;
scanf("%d\n",&tc);
for(int t=0;t<tc;t++) {
int n,m;
scanf("%d %d\n",&n,&m);
if (n==1) {
printf("0\n");
}
else if (n==2) {
printf("%d\n",m);
}
else {
printf("%d\n",m*2);
}
}
}
아주 자명한 그리디이다. a의 가장 작은 수와 b의 가장 큰 수를 스왑해주는 연산을 k번 수행하자. a의 가장 작은 수가 b의 가장 큰 수보다 크면 수행을 멈춘다. 구현은 우선순위 큐를 이용하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int tc;
scanf("%d\n",&tc);
for(int t=0;t<tc;t++) {
int n,k;
scanf("%d %d\n",&n,&k);
priority_queue<int,vector<int>,greater<int>> a;
priority_queue<int> b;
for(int i=0;i<n;i++) {
int x;
scanf("%d",&x);
a.push(x);
}
for(int i=0;i<n;i++) {
int x;
scanf("%d",&x);
b.push(x);
}
for(int i=0;i<k;i++) {
int mini=a.top();
int maxi=b.top();
if (mini>maxi) {
break;
}
a.pop();
b.pop();
b.push(mini);
a.push(maxi);
}
int sum=0;
for(int i=0;i<n;i++) {
sum+=a.top();
a.pop();
}
printf("%d\n",sum);
}
}
직관적으로 중심의 점으로 모든 점을 모으는 것이 최적임을 알 수 있다. 증명은 생략한다.
저 식이 어떻게 성립되는지는 잘 생각해보자.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int tc;
scanf("%d\n",&tc);
for(int t=0;t<tc;t++) {
long long n;
scanf("%lld\n",&n);
long long ret=0;
for(long long i=1;i<n;i+=2) {
ret+=n*n-i*i;
}
printf("%lld\n",ret);
}
}
대회 중에 푼 코드.
길이와 시작점을 넣어두고 적당히 우선순위 큐로 관리해주자. 그럼 끝이다.
#include <bits/stdc++.h>
using namespace std;
int n;
typedef pair<int,int> P;
int cnt=0;
int ret[300005];
int main(void) {
int tc;
scanf("%d\n",&tc);
for(int t=0;t<tc;t++) {
cnt=0;
scanf("%d\n",&n);
priority_queue<P> pq;
pq.push(P(n-1,0));
while (!pq.empty()) {
int l=-pq.top().second;
int r=l+pq.top().first;
int mid=(l+r)/2;
pq.pop();
ret[mid]=++cnt;
if (l<=mid-1) {
pq.push(P(mid-1-l,-l));
}
if (mid+1<=r) {
pq.push(P(r-mid-1,-mid-1));
}
}
for(int i=0;i<n;i++) {
printf("%d ",ret[i]);
}
printf("\n");
}
}
인덱스의 나머지가 x인 부분에만, k 간격으로 1이 존재해야 한다.
먼저 모든 수를 0으로 바꾼다고 가정해보자. 그러면 필요한 연산 횟수는 1의 개수만큼이다.
이제 이걸 베이스로 생각한다.
여기서 나머지 x를 고정하고 생각해보자.
나머지가 x인 인덱스들을 나열하면 우리는 k 간격으로 1이 존재하게 하는 것을 적절히 구간을 정하는 것으로 환원할 수 있다.
그리고 구간에 대한 수를 1로 바꿀 때 드는 비용에 대해 알아보자.
구간에 있는 0은 원래 연산이 필요없었지만 필요해져서 1의 연산을 추가로 요구한다. 구간에 있는 1은 원래 연산이 필요했지만 필요없어져서 1의 연산을 절약할 수 있다.
이제 이걸 minimum subarray 문제로 다시 환원할 수 있다.
시간복잡도는 O(k*n/k)=O(n)
#include <bits/stdc++.h>
using namespace std;
int arr[1000000];
int main(void) {
int tc;
scanf("%d\n",&tc);
for(int t=0;t<tc;t++) {
int n,k;
scanf("%d %d\n",&n,&k);
int ret=n;
int sum=0;
for(int i=0;i<n;i++) {
scanf("%1d",&arr[i]);
}
for(int i=0;i<n;i++) {
sum+=arr[i];
}
ret=sum;
for(int i=0;i<k;i++) {
vector<int> v;
for(int j=i;j<n;j+=k) {
if (arr[j]==1) {
v.push_back(-1);
}
else {
v.push_back(1);
}
}
int val=0;
for(int j=0;j<v.size();j++) {
val=min(v[j],val+v[j]);
ret=min(ret,sum+val);
}
}
printf("%d\n",ret);
}
}
일단 문제가 약간 복잡하니 살짝 바꾼다.
약간의 관찰을 한다.
"한 번 이동할 때 i+j의 값은 무조건 1씩 증가한다."
그러면 a[i][j]=a[i][j]-i-j;를 시행한다.
이제 a[i][j]가 모두 같은 경로를 만드는 것이 목표가 된다.
그럼 이제 경로상에서 모두 같은 a[i][j]를 x로 고정하다.
이때 최적의 후보인 x는 a[i][j]에 등장하는 n*m개의 수들이다.
그러면 O(nm) dp를 nm번 돌리자.
dp식은 다음과 같이 정의할 수 있다.
a[i][j]<x인 경우:
dp[i][j]=INF
a[i][j]>=x인 경우:
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j]-x
dp[i][j]는 경로상의 값이 모두 x이게 (i,j)까지 경로를 잇는데 필요한 비용이다.
O(n^2m^2)에 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
long long arr[100][100];
long long dp[100][100];
const long long INF=1e18;
int n,m;
bool valid(int x,int y) {
return x>=0&&x<n&&y>=0&&y<m;
}
int main(void) {
int tc;
scanf("%d\n",&tc);
for(int t=0;t<tc;t++) {
scanf("%d %d\n",&n,&m);
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
scanf("%lld ",&arr[i][j]);
arr[i][j]-=i+j;
}
scanf("\n");
}
long long ret=INF;
for(int one=0;one<n;one++) {
for(int two=0;two<m;two++) {
long long val=arr[one][two];
if (arr[0][0]<val) {
continue;
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
dp[i][j]=INF;
}
}
dp[0][0]=arr[0][0]-val;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if (arr[i][j]>=val) {
if (valid(i-1,j)) {
dp[i][j]=min(dp[i][j],dp[i-1][j]+arr[i][j]-val);
}
if (valid(i,j-1)) {
dp[i][j]=min(dp[i][j],dp[i][j-1]+arr[i][j]-val);
}
}
}
}
ret=min(ret,dp[n-1][m-1]);
}
}
printf("%lld\n",ret);
}
}
'PS' 카테고리의 다른 글
| NYPC 2020 예선 풀이 (1) | 2020.09.06 |
|---|---|
| 2020.06.28 Problem Solving (2) | 2020.06.28 |
| BAPC 2019 (0) | 2020.05.11 |
| 백준 18195번 정점 찾기 (0) | 2020.05.10 |
| BAPC 2016 (0) | 2020.05.06 |
