가치가 100인 동전을 500/100 =5개보다 적게 사용한 것이 정답이다 100원 동정을 5개 사용했다면 500개 1개로 변경하면 더 최소가된다.
모든 정답 중에서 Ai를 사용하지 않고 만든 것 중 K의 최댓값은 Ai-1이다. 100을 사용하지 않고 만든 것 중 최댓값은 99이다. Ai를 넘는 K의 값을 구하려면 Ai를 필수로 1개 이상 사용해야 한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int main() {
cin >> n;
vector<int> time(n);
for (int i = 0; i < n; i++)
cin >> time[i];
sort(time.begin(), time.end());
for (int i = 0; i < n - 1; i++)
time[i + 1] += time[i];
int ret = 0;
for (int i = 0; i < n; i++)
ret += time[i];
cout << ret << endl;
return 0;
}
걸리는 시간을 오름차순으로 정렬하여 대기 시간의 합을 구하면 된다.
앞에 있는 사람의 기다리는 시간이 짧을 수록, 그 시간에 영향을 받는 사람들의 대기 시간이 전체적으로 짧아지므로 오름차순 정렬을 하는 것이다.
각각의 시간을 p1, p2, p3, p4, p5라고 했을 때, 총 대기 시간 S = p1 + (p1 + p2) + (p1 + p2 + p3) + .. 이므로 S = 5p1 + 4p2 + 3p3 + 2p4 + p5이다.
같은 위치를 두 번 뒤집으면 원상복귀된다. 따라서 한 칸에 대해서 변환 연산을 사용하지 않거나, 한 번 사용한다. 이렇게 스위치를 키고 끄거나, 문을 열고 닫거나와 같이 1과 0을 반복하는 연산에서는 같은 행위를 중복하는 것이 의미가 없음을 기억하자.
이제, 이 문제는 각각의 칸에서 만들어지는 3x3행렬을 사용할지 말지로 선택하는 문제로 바뀐다. ⇒ O(2의 NM승)
여기서 한 칸에 대해서 반복 연산하는 것이 소용 없음을 이용해 연산을 줄일 수 있다. 가장 왼쪽 위 칸은, 자신을 포함하는 3x3 부분행렬 중 자신이 가장 왼쪽 위에 위치하는 부분행렬에 의해서만 바뀔 수 있다. 따라서 A[0][0] == B[0][0]이라면 이 칸을 건들이면 안되고, 건든다면 딱 한번만 건들 수 있다.
이렇게 (N-2) x (M-2)칸에 대해 그 칸을 왼쪽 위로 하고 있는 3x3 부분행렬을 만들어 A[i][j]와 B[i][j]를 검사하고, 다르면 flip ****하는 과정을 거쳤다고 하자. (N-2) x (M-2)칸을 제외한 나머지 칸을 건들이면, (N-2) x (M-2)칸이 침범되므로, 이 부분이 B와 다르면 그건 바꿀 수 없는 경우가 되는 것이다.
#include <iostream>
#pragma warning (disable:4996)
using namespace std;
int n, m;
int A[51][51];
int B[51][51];
void flip(int y, int x) {
for (int i = y - 1; i <= y + 1; i++)
for (int j = x - 1; j <= x + 1; j++)
A[i][j] = 1 - A[i][j];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%1d", &A[i][j]);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%1d", &B[i][j]);
int ret = 0;
for(int i = 0; i < n-2 ; i++)
for (int j = 0; j < m - 2; j++)
if (A[i][j] != B[i][j]) {
ret++;
flip(i + 1, j + 1);
}
for(int i = 0; i < n; i++)
for(int j= 0;j < m;j++)
if (A[i][j] != B[i][j]) {
cout << -1 << endl;
return 0;
}
cout << ret << endl;
}