Rotation시키는 것은, 돌아가는 원판에 있는 숫자들을 다 저장해놓고, 한칸씩 더 이동시켜서 다시 넣는 방식으로 했으며
왼쪽위 오른쪽위, 오른쪽아래, 왼쪽아래 꼭지점을 기준으로
해당 꼭지점에 다다를때 이동방향을 바꾸는 식으로 구현해보았습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int A[55][55];
typedef struct _Rot {
int r, c, s;
} Rot;
Rot rot[10];
int N, M, K;
int ans;
void get_input();
bool used[10];
int order[10];
void copy(int A[][55], int B[][55]);
const int dx[] = { +0, +1, +0, -1 };
const int dy[] = { +1, +0, -1, +0 };
void _rotate(int B[][55], int row, int col, int rad) {
vector<int> val;
int x = row - rad;
int y = col - rad;
int cnt = rad * 8;
set<pii> check;
check.insert(make_pair(row + rad, col + rad));
check.insert(make_pair(row - rad, col + rad));
check.insert(make_pair(row + rad, col - rad));
int k = 0;
for (int i = 0; i < cnt; i++) {
val.push_back(B[x][y]);
x += dx[k];
y += dy[k];
if (check.find(make_pair(x, y)) != check.end()) {
k++;
}
}
k = 0;
x = row - rad;
y = col - rad;
x += dx[0];
y += dy[0];
for (int i = 0; i < cnt; i++) {
B[x][y] = val[i];
x += dx[k];
y += dy[k];
if (check.find(make_pair(x, y)) != check.end()) {
k++;
}
}
}
void rotate(int B[][55], int row, int col, int rad) {
for (int i = 1; i <= rad; i++) {
_rotate(B, row - 1, col - 1, i);
}
}
void dfs(int p) {
if (p < K) {
for (int i = 0; i < K; i++) {
if (used[i] == false) {
used[i] = true;
order[p] = i;
dfs(p + 1);
used[i] = false;
}
}
}
else {
//do simulation
int B[55][55];
copy(B, A);
for (int i = 0; i < K; i++) {
auto& o = rot[order[i]];
rotate(B, o.r, o.c, o.s);
}
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < M; j++) {
sum += B[i][j];
}
ans = min(ans, sum);
}
}
}
int main() {
ans = 987654321;
get_input();
dfs(0);
cout << ans << endl;
}
void get_input() {
cin >> N >> M >> K;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> A[i][j];
for (int i = 0; i < K; i++) {
auto& R = rot[i];
cin >> R.r >> R.c >> R.s;
}
}
void copy(int A[][55], int B[][55]) {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
A[i][j] = B[i][j];
}
}
B번 문제입니다. 사과의 풍미(flavor) 값은 연속된 수열 값으로 나타납니다. 전체 값 중에서 사과 하나를 뺏을 때 차이가 가장 적을려면, 전체 값 중에 절대값이 가장 작은 것을 하나 빼버리면 됩니다.
O(N)으로 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
int N, L;
cin >> N >> L;
int S = (N - 1) * N / 2 + N * L;
int dect = 987654321;
for (int i = 0; i < N; i++) {
int cand = i + L;
if (abs(cand) < abs(dect)) {
dect = cand;
}
}
cout << (S - dect) << endl;
}
(전체) - (C로 나누어 떨어지는 수) - (D로 나누어 떨어지는 수) + (C와 D 둘다 나누어 떨어지는 수)
가 됩니다.
C와 D 둘다 나누어 떨어지는 수는 C와 D의 LCM(최소공배수)으로 나누어 떨어지는 수와 같습니다.
C와 D의 최소 공배수는 C*D / gcd(C, D)와 같습니다.
gcd(C, D)는 C와 D의 최대공약수를 뜻합니다.
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
template<class T>
T gcd(T a, T b)
{
if (b == 0) return a;
a %= b;
return gcd(b, a);
}
int main() {
ll A, B, C, D;
cin >> A >> B >> C >> D;
ll total = B - A + 1;
ll Cdiv = B / C - ((A - 1) / C);
ll Ddiv = B / D - ((A - 1) / D);
ll LCM = C * D / gcd(C, D);
ll CDdiv = B / LCM - ((A - 1) / LCM);
ll ans = total - Cdiv - Ddiv + CDdiv;
cout << ans << endl;
}
E번 문제입니다. 문제 내용을 잘못 이해해서 좀 해맸었는데, 일단 N개의 vertex로 shortest path = 2인 pair를 최대한 많이 만드는 구성을 한번 생각해봤습니다.
N=7이라 한다면, 대충 위와 같이 생겼을 때 가장 많은 shortest path = 2인 쌍이 생깁니다. 1을 제외한 모든 조합들이 가능한거죠.
즉 //(\dbinom{6}{2}//)개 만큼 생깁니다.
N에 대하여 일반화를 하면 //(\dbinom{N-1}{2}//)가지가 나오는 것이죠. 요렇게 나오는 경우가 최대 경우입니다.
따라서 //(K > \dbinom{N-1}{2} //)이면 불가능한 경우입니다.
그렇다면 저 최대값 이하의 값은 다 만들수가 있느냐?
이에 대한 답은 Yes입니다. 위 그림에서 예를 들어 4와 5를 연결해버리면, 4에서 5로 가는 최단거리가 1이 되어서, 만족하는 쌍의 수가 하나 줄게 됩니다. 그리고 그 추가된 Edge는 다른 pair들에는 전혀 영향을 끼치지 않죠. 이런식으로 하나하나씩 줄여서 K값을 0으로 만들수도 있습니다.
따라서 N값에 따라서 0~최대값까지 죄다 만들 수 있는 것이죠. 이 범위 안에 들어있다면 저런 형태의 graph를 리턴하고, 그렇지 않다면 불가능하다라고 출력하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
int N, K;
cin >> N >> K;
int maxi = (N - 1)*(N - 2) / 2;
if (K > maxi) {
cout << -1;
return 0;
}
int M = N - 1;
int diff = maxi - K;
cout << (M + diff) << endl;
for (int i = 0; i < M; i++) {
cout << 1 << ' ' << i + 2 << endl;
}
int src = 2;
int dst = 3;
for (int i = 0; i < diff; i++) {
cout << src << ' ' << dst << endl;
dst++;
if (dst == N + 1) {
src++;
dst = src + 1;
}
}
}
