* 숫자 재배치 (low) : 두 정수 a, b가 주어지고 a에 포함된 숫자를 섞어서 새로운 수 c를 만든다고 할 때 b보다 작거나 같으면서 가장 큰 c값을 구하는 문제다.
16943번: 숫자 재배치
두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보�
www.acmicpc.net
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
string a;
int b;
int ans = -1;
cin >> a >> b;
sort(a.begin(), a.end());
do {
int c = stoi(a);
if (c <= b && a[0] != '0') {
if (ans == -1 || ans < c) ans = c;
}
} while (next_permutation(a.begin(), a.end()));
cout << ans << '\n';
return 0;
}- 가장 직관적인 방법은 next_permutation 함수를 사용하는 것이다. 순서대로 구해서 값을 비교해주면 된다.
- a를 배열에 담아서 재귀로도 해결이 가능하다.
#include <iostream>
#include <string>
using namespace std;
int a[10];
bool check[10];
int b;
int n;
int go(int idx, int num) {
if (idx == n) return num;
int ans = -1;
for (int i = 0; i < n; i++) {
if (check[i]) continue;
if (idx == 0 && a[i] == 0) continue;
check[i] = true;
int temp = go(idx + 1, num * 10 + a[i]);
if (temp < b && ans < temp) ans = temp;
check[i] = false;
}
return ans;
}
int main()
{
string s;
cin >> s;
n = s.size();
for (int i = 0; i < n; i++) {
a[i] = s[i] - '0';
}
cin >> b;
cout << go(0, 0) << '\n';
return 0;
}- 누적값에 10을 곱해서 다음 수를 더해주는 식으로 값을 만들어가면 된다.
* 괄호 추가하기 (mid) : 괄호를 적절히 추가해 만들 수 있는 식의 최댓값을 구하는 문제다.
16637번: 괄호 추가하기
길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순�
www.acmicpc.net
- 괄호 안에는 연산자가 하나만 들어있을 수 있고, 괄호 수 제한은 없다는 조건에 유의해서 풀자.
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
int n, ans;
string a;
int cal(int a1, int a2, char op) {
if (op == '+') return a1 + a2;
if (op == '-') return a1 - a2;
if (op == '*') return a1 * a2;
}
void go(int idx, int now) {
if (idx > n - 1) {
ans = max(ans, now);
return;
}
char oper = (idx == 0) ? '+' : a[idx - 1];
if (idx + 2 < n) { // 괄호 추가해서 계산하고 다음 인덱스로
int p = cal(a[idx] - '0', a[idx + 2] - '0', a[idx + 1]);
go(idx + 4, cal(now, p, oper));
} // 괄호 없이 현재 위치의 수까지만 계산하고 다음 인덱스로
go(idx + 2, cal(now, a[idx] - '0', oper));
}
int main()
{
cin >> n >> a;
// 정답이 -2^31 이상 2^31 이하고, 최댓값을 구하는 것이므로
// ans를 INT_MIN으로 초기화 해준다.
ans = INT_MIN;
go(0, 0);
cout << ans << '\n';
return 0;
}
* 감시 (mid) : CCTV가 감시하지 못하는 사각지대의 최소 크기를 구하는 문제다.
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감��
www.acmicpc.net
- 1, 3, 4 번은 4가지, 2번은 2가지, 5번은 1가지 경우가 가능하다. CCTV는 감시하는 방향에 있는 칸 전체를 감시할 수 있고, 벽(6번)을 통과할 수는 없다. 또한 CCTV는 회전이 가능하다. 방향을 적절히 정해서 사각 지대의 최소 크기를 구하면 된다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct ct {
int x;
int y;
int num;
};
int n, m;
int bs;
int a[8][8];
int b[8][8];
vector<ct> id;
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int cinsert(int x, int y, int d) {
int cnt = 0;
int nx = x + dx[d], ny = y + dy[d];
while (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (b[nx][ny] == -1) break;
if (b[nx][ny] == 0) cnt += 1;
b[nx][ny] += 1;
nx += dx[d]; ny += dy[d];
}
return cnt;
}
void cerase(int x, int y, int d) {
int nx = x + dx[d], ny = y + dy[d];
while (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (b[nx][ny] == -1) break;
if (b[nx][ny] != 0) b[nx][ny] -= 1;
nx += dx[d]; ny += dy[d];
}
return;
}
void go(int idx, int bs_cnt) {
if (idx == id.size()) {
bs = min(bs, bs_cnt);
return;
}
int nx = id[idx].x;
int ny = id[idx].y;
int num = id[idx].num;
if (id[idx].num == 1) {
for (int i = 0; i < 4; i++) {
go(idx + 1, bs_cnt - cinsert(nx, ny, i));
cerase(nx, ny, i);
}
}
else if (id[idx].num == 2) {
for (int i = 0; i < 2; i++) {
int count = cinsert(nx, ny, i * 2) + cinsert(nx, ny, i * 2 + 1);
go(idx + 1, bs_cnt - count);
cerase(nx, ny, i * 2);
cerase(nx, ny, i * 2 + 1);
}
}
else if (id[idx].num == 3) {
for (int i = 0; i < 4; i++) {
int count;
if(i % 2 == 0) count = cinsert(nx, ny, i / 2) + cinsert(nx, ny, 2);
else count = cinsert(nx, ny, i / 2) + cinsert(nx, ny, 3);
go(idx + 1, bs_cnt - count);
if (i % 2 == 0) {
cerase(nx, ny, i / 2);
cerase(nx, ny, 2);
}
else {
cerase(nx, ny, i / 2);
cerase(nx, ny, 3);
}
}
}
else if (id[idx].num == 4) {
for (int i = 0; i < 4; i++) {
int count = 0;
if (i < 2) count = cinsert(nx, ny, i) + cinsert(nx, ny, 2) + cinsert(nx, ny, 3);
else count = cinsert(nx, ny, i) + cinsert(nx, ny, 0) + cinsert(nx, ny, 1);
go(idx + 1, bs_cnt - count);
if (i < 2) {
cerase(nx, ny, i);
cerase(nx, ny, 2);
cerase(nx, ny, 3);
}
else {
cerase(nx, ny, i);
cerase(nx, ny, 0);
cerase(nx, ny, 1);
}
}
}
else {
int count = 0;
for (int i = 0; i < 4; i++) {
count += cinsert(nx, ny, i);
}
go(idx + 1, bs_cnt - count);
for (int i = 0; i < 4; i++) {
cerase(nx, ny, i);
}
}
return;
}
int main()
{
cin >> n >> m;
int cnt = n*m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
if (a[i][j] != 0) {
cnt -= 1;
if (a[i][j] == 6) {
b[i][j] = -1;
continue;
}
b[i][j] = 1;
ct tmp;
tmp.x = i; tmp.y = j; tmp.num = a[i][j];
id.push_back(tmp);
}
}
}
bs = cnt;
go(0, cnt);
cout << bs << '\n';
return 0;
}- 현재 사각지대의 수를 구한 뒤에, CCTV의 감시 범위에 따라 하나씩 빼주는 방식으로 계산했다.
- b에서는 누적된 cctv의 범위를 계산해줬다. 0이면 사각지대이고, cinsert를 이용해 누적해서 더해준 값은 cerase를 이용해 다시 빼준다. cinsert에서는 방향이 정해지면 벽이나 경계가 나올 때까지 범위를 설정해주고, 새롭게 추가된 범위를 카운트해서 리턴한다. 이를 현재 사각지대 값에 빼주기 위함이다. 재귀를 다 돌고나면 똑같은 범위에서 cerase를 수행해주고 값을 이전으로 돌린다.
* 등차수열 변환 (mid) : 각 수에 +1 혹은 -1 연산이 허용된다고 할 때, 최소 연산으로 등차수열을 만드는 법을 구하기.
17088번: 등차수열 변환
크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]��
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a;
int min_ans = -1;
int main()
{
cin >> n;
int t;
for (int i = 0; i < n; i++) {
cin >> t;
a.push_back(t);
}
for (int d1 = -1; d1 <= 1; d1++) {
for (int d2 = -1; d2 <= 1; d2++) {
int cnt = 0;
int a0 = a[0] + d1;
int d = a[1] + d2 - a0;
if (d1 != 0) cnt += 1;
if (d2 != 0) cnt += 1;
bool okay = true;
int an = a0 + d;
for (int i = 2; i < n; i++) {
an += d;
if (a[i] == an) continue;
if (a[i] - 1 == an || a[i] + 1 == an) cnt += 1;
else {
okay = false;
break;
}
}
if (okay) {
if (min_ans == -1 || min_ans > cnt) min_ans = cnt;
}
}
}
cout << min_ans << '\n';
return 0;
}- 첫번째, 두번째 항에 각각 연산을 하지 않을 때와 +1, -1 연산을 했을 때의 공차가 다르므로 총 9가지 공차를 기준으로 계산을 해본다. 두번째 항부터 공차를 더해가며 연산이 필요한 경우를 체크한다. 연산으로 해결되지 않는다면 그 경우는 조건을 만족하지 않으므로 반복문을 중단하고 다음 경우로 넘어간다.
* 치킨 배달 (mid) : 도시의 '치킨 거리'의 최솟값을 구하는 문제다.
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
- 도시의 치킨 거리는 도시 안의 각 집에서 가장 가까운 치킨집과의 거리를 더한 합을 말한다. (r1,c1), (r2,c2)의 거리는 |r1-r2| + |c1-c2| 와 같이 구한다.
- 가능한 치킨집의 수는 최대 13개이고, 도시의 크기 n*n에서 n은 최대 50까지 가능하다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int a[50][50];
vector<pair<int,int>> h;
vector<pair<int, int>> c;
int min_ans = -1;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
if (a[i][j] == 1) {
h.push_back({ i,j });
}
if (a[i][j] == 2) {
c.push_back({ i,j });
}
}
}
int hsize = h.size();
int csize = c.size();
for (int i = 1; i < (1 << csize); i++) {
vector<int> dist(hsize, -1);
int cnt = 0;
for (int j = 0; j < csize; j++) { //치킨
if (i&(1 << j)) {
cnt += 1;
for (int k = 0; k < hsize; k++) { // 집
int tmp = abs(c[j].first - h[k].first) + abs(c[j].second - h[k].second);
if (dist[k] == -1 || dist[k] > tmp) dist[k] = tmp;
}
}
}
if (cnt <= m) {
int sum = 0;
for (int d : dist) {
sum += d;
}
if (min_ans == -1 || min_ans > sum) min_ans = sum;
}
}
cout << min_ans << '\n';
return 0;
}- h에는 집의 위치를, c에는 치킨집의 위치를 저장한다. 비트 연산을 통해 선택된 치킨집에서 집까지의 거리를 계산해주고 최솟값일 때 갱신해준다.
- 최대 m개까지 선택이 가능하다는 조건을 만족할 때, 도시의 치킨 거리와 비교해서 값을 갱신해준다.
* 숫자판 점프 (mid) : 임의의 위치에서 시작해 인접한 네 방향으로 다섯번 이동해서 만들 수 있는 6자리 수의 개수.
2210번: 숫자판 점프
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.
www.acmicpc.net
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
vector<string> a[5];
bool check[1000000];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans = 0;
void dfs(int x, int y, string now) {
int n = now.size();
if (n == 6) {
if (check[stoi(now)] == false) {
check[stoi(now)] = true;
ans += 1;
}
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
dfs(nx, ny, now + a[nx][ny]);
}
}
int main()
{
string c;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cin >> c;
a[i].push_back(c);
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
dfs(i, j, a[i][j]);
}
}
cout << ans << '\n';
return 0;
}- 5*5로 크기가 고정되어 그리 어렵지 않았다. dfs를 어렵지 않게 풀 수 있다.
* 테트리스 (mid) : 현재 놓여진 위치에 맞게 블록을 떨어트리는 방법의 수를 구하는 문제다.
3019번: 테트리스
테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다. 블록을 떨어뜨리기 전에
www.acmicpc.net
- 완전 노가다다. 블록 별로 경우의 수를 모두 설정해주면 된다. 손이 많이 가는 문제였다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int c, p;
int high[100];
int ans = 0;
void blocks(int num) {
if (num == 1) {
for (int k = 0; k < 2; k++) {
for (int i = 0; i < c; i++) {
if (k == 0) { // 세로
ans += 1;
}
else { // 가로
if (i + 3 < c) {
if ((high[i] == high[i + 1]) && (high[i + 1] == high[i + 2])
&& high[i + 2] == high[i + 3])
ans += 1;
}
}
}
}
}
else if (num == 2) {
for (int i = 0; i < c; i++) {
if (i + 1 < c) {
if (high[i] == high[i + 1])
ans += 1;
}
}
}
else if (num == 3) {
for (int k = 0; k < 2; k++) {
for (int i = 0; i < c; i++) {
if (k == 0) { // 가로
if (i + 2 < c) {
if ((high[i] == high[i + 1]) && (high[i + 1] + 1 == high[i + 2]))
ans += 1;
}
}
else { // 세로
if (i + 1 < c) {
if (high[i] == high[i+1] + 1)
ans += 1;
}
}
}
}
}
else if (num == 4) {
for (int k = 0; k < 2; k++) {
for (int i = 0; i < c; i++) {
if (k == 0) { // 가로
if (i + 2 < c) {
if ((high[i] == high[i + 1] + 1) && (high[i + 1] == high[i + 2]))
ans += 1;
}
}
else { // 세로
if (i + 1 < c) {
if (high[i] + 1 == high[i + 1])
ans += 1;
}
}
}
}
}
else if (num == 5) {
for (int k = 0; k < 4; k++) {
for (int i = 0; i < c; i++) {
if (k == 0) {
if (i + 2 < c) {
if ((high[i] == high[i + 1]) &&(high[i + 1] == high[i + 2]))
ans += 1;
}
}
else if (k == 1) {
if (i + 1 < c) {
if (high[i] + 1 == high[i + 1])
ans += 1;
}
}
else if (k == 2) {
if (i + 2 < c) {
if ((high[i] == high[i + 2]) && (high[i] == high[i + 1] + 1))
ans += 1;
}
}
else {
if (i + 1 < c) {
if (high[i] == high[i + 1] + 1)
ans += 1;
}
}
}
}
}
else if (num == 6) {
for (int k = 0; k < 4; k++) {
for (int i = 0; i < c; i++) {
if (k == 0) {
if (i + 2 < c) {
if ((high[i] == high[i + 1]) && (high[i + 1] == high[i + 2]))
ans += 1;
}
}
else if (k == 1) {
if (i + 1 < c) {
if (high[i] == high[i + 1])
ans += 1;
}
}
else if (k == 2) {
if (i + 2 < c) {
if ((high[i + 1] == high[i + 2]) && (high[i] + 1 == high[i + 1]))
ans += 1;
}
}
else {
if (i + 1 < c) {
if (high[i] == high[i + 1] + 2)
ans += 1;
}
}
}
}
}
else if (num == 7) {
for (int k = 0; k < 4; k++) {
for (int i = 0; i < c; i++) {
if (k == 0) {
if (i + 2 < c) {
if ((high[i] == high[i + 1]) && (high[i + 1] == high[i + 2]))
ans += 1;
}
}
else if (k == 1) {
if (i + 1 < c) {
if (high[i] == high[i + 1])
ans += 1;
}
}
else if (k == 2) {
if (i + 2 < c) {
if ((high[i] == high[i + 1]) && (high[i + 1] == high[i + 2] + 1))
ans += 1;
}
}
else {
if (i + 1 < c) {
if (high[i] + 2 == high[i + 1])
ans += 1;
}
}
}
}
}
}
int main()
{
cin >> c >> p;
for (int i = 0; i < c; i++) cin >> high[i];
blocks(p);
cout << ans << '\n';
return 0;
}
* 한윤정이 ~ (mid) : 특정 조합을 피해 아이스크림 3개를 선택하는 문제다.
2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 ��
www.acmicpc.net
- 아이스크림이 최대 200개까지 가능하므로, 삼중 for문을 사용하면 쉽게 풀린다. a, b, c를 골랐을 때 a,b / a,c / b,c 가 최악의 조합이 아니면 카운트 해주면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, m;
int ans = 0;
bool check[201][201];
int main()
{
cin >> n >> m;
int ic1, ic2;
for (int i = 0; i < m; i++) {
cin >> ic1 >> ic2;
check[ic1][ic2] = true;
check[ic2][ic1] = true;
}
for (int i = 1; i <= n - 2; i++) {
for (int j = i + 1; j <= n - 1; j++) {
for (int k = j + 1; k <= n; k++) {
if (check[i][j] || check[j][k] || check[i][k]) continue;
ans += 1;
}
}
}
cout << ans << '\n';
return 0;
}
* N*M 보드 완주하기 (high) : 방향을 바꿔가며 쭉 이동할 때, 방향 이동을 최소로 해서 모든 칸을 방문하는 경우.
9944번: NxM 보드 완주하기
N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져
www.acmicpc.net
- 한번 방향을 정하면 장애물이나 벽이 나올 때까지 계속 이동한다. 그 다음 방향은 규칙이 따로 없고 적절하게 이동해야 한다. 결국 모든 방향으로 다 이동해봐야 한다.
- 많이 헤매봐도 답을 구하기가 힘들어 답안 코드를 참조했다.
#include <iostream>
using namespace std;
char a[33][33];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int n, m;
bool ok(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
int go(int x, int y, int cnt) {
int ans = -1;
if (cnt == 0) {
return 0;
}
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
while (ok(nx, ny) && a[nx][ny] == '.') {
a[nx][ny] = '#';
cnt -= 1;
nx += dx[k];
ny += dy[k];
}
nx -= dx[k];
ny -= dy[k];
if (!(x == nx && y == ny)) {
int temp = go(nx, ny, cnt);
if (temp != -1) {
if (ans == -1 || ans > temp+1) {
ans = temp+1;
}
}
}
while (!(x == nx && y == ny)) {
a[nx][ny] = '.';
cnt += 1;
nx -= dx[k];
ny -= dy[k];
}
}
return ans;
}
int main() {
int tc = 1;
while (cin >> n >> m) {
int cnt = 0;
for (int i=0; i<n; i++) {
cin >> a[i];
for (int j=0; j<m; j++) {
if (a[i][j] == '.') {
cnt += 1;
}
}
}
int ans = -1;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (a[i][j] == '.') {
a[i][j] = '#';
int temp = go(i, j, cnt-1);
if (temp != -1) {
if (ans == -1 || ans > temp) {
ans = temp;
}
}
a[i][j] = '.';
}
}
}
cout << "Case " << tc << ": " << ans << '\n';
tc += 1;
}
return 0;
}
- 이 코드 역시 앞에서 풀었던 '감시' 문제와 마찬가지로 앞으로 방문해야 할 칸의 수를 구해서 이동할 때마다 하나씩 빼면서 방문해야 할 칸이 0일 때까지 이동해주면 된다.
- 빈칸을 만나면 '#'을 넣어주고 방문할 칸에 -1을 한 뒤에 재귀 함수를 돌려준다. 다음 칸이 범위 안이고, 빈칸일 때까지 빈칸에 '#' 넣고, 방문할 칸의 수에 -1을 반복해준다. 제자리 걸음하지 않았다면, 현재 위치와 방문해야 할 칸을 인수로 넣고 재귀를 해준다.
- temp에는 이전의 이동을 제외한 이후의 이동 횟수가 담길 것이므로, temp + 1 이 이동 횟수다. 이를 이용해 최솟값을 갱신해준다. 갱신이 끝나면 '#'으로 바꾼 칸을 '.'으로, 이동해야 할 횟수도 그대로 리셋해준다.
* 세 친구 (mid) : 사람 a,b,c를 고를 때 각각의 친구 수 합을 구하는 문제다.
17089번: 세 친구
첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친�
www.acmicpc.net
- a, b, c는 서로 친구이고, 각각의 친구 관계는 제외해야 하는 조건이 있다. 다시 말해 각각 친구 중 b, c / a, c / a, b를 제외한 친구의 합을 구하라는 거다. 그냥 전체 친구의 합을 구해서 -6을 하면 된다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
bool a[4001][4001];
int ans = -1;
int main()
{
cin >> n >> m;
int f1, f2;
for (int i = 0; i < m; i++) {
cin >> f1 >> f2;
a[f1][f2] = true;
a[f2][f1] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i][j] == false) continue;
for (int k = j + 1; k <= n; k++) {
if (a[i][k] == false || a[j][k] == false) continue;
int sum = -6;
for (int l = 1; l <= n; l++) {
if (a[i][l]) sum += 1;
if (a[j][l]) sum += 1;
if (a[k][l]) sum += 1;
}
if (ans == -1 || ans > sum)ans = sum;
}
}
}
cout << ans << '\n';
return 0;
}
* 배열 돌리기 4 (mid) : 순서를 바꿔가며 회전시킨 배열에서 행 합의 최솟값을 구하면 된다.
17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
- 회전 연산 계산하는 게 까다로웠다. 근데 위에서 푼 '테트리스' 문제처럼 원리만 이해하고 나니 어렵지 않게 풀렸다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct turn {
int tr;
int tc;
int ts;
};
int n, m, k;
vector<vector<int>>a(51, vector<int>(51));
vector<vector<int>>init_a(51, vector<int>(51));
vector<turn> b;
int ans = -1;
int find_min() {
int amin = -1;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= m; j++) {
sum += a[i][j];
}
if (amin == -1 || amin > sum) amin = sum;
}
return amin;
}
void rotation(int k) {
int sx = b[k].tr - b[k].ts;
int sy = b[k].tc - b[k].ts;
int sx2 = b[k].tr + b[k].ts;
int sy2 = b[k].tc + b[k].ts;
while (!(sx == b[k].tr && sy == b[k].tc)) {
int now = a[sx + 1][sy];
int next;
for (int i = sy; i < sy2; i++) { // 위
next = a[sx][i];
a[sx][i] = now;
now = next;
}
for (int i = sx; i < sx2; i++) { // 오른쪽
next = a[i][sy2];
a[i][sy2] = now;
now = next;
}
for (int i = sy2; i > sy; i--) { // 아래
next = a[sx2][i];
a[sx2][i] = now;
now = next;
}
for (int i = sx2; i > sx; i--) { // 왼쪽
next = a[i][sy];
a[i][sy] = now;
now = next;
}
sx += 1; sy += 1;
sx2 -= 1; sy2 -= 1;
}
return;
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
init_a = a;
int r, c, s;
vector<int> idx;
for (int i = 0; i < k; i++) {
cin >> r >> c >> s;
turn temp;
temp.tr = r; temp.tc = c; temp.ts = s;
b.push_back(temp);
idx.push_back(i);
}
sort(idx.begin(), idx.end());
do {
for (int i = 0; i < k; i++) {
rotation(idx[i]);
}
int temp = find_min();
if (ans == -1 || ans > temp) ans = temp;
a = init_a;
} while (next_permutation(idx.begin(), idx.end()));
cout << ans << '\n';
return 0;
}
-
정리해보니 문제가 참 많았다. 뭔가 많이 헤맸던 챕터였다.
일주일 정도 지나면 내 취준 생활에서 가장 중요한 순간을 맞이한다.
결과에 따라 알고리즘 강의 진행 양상도 달라질 것 같다.
일단은 지켜보면서, 귀중한 기회를 놓치지 않도록 열심히 준비해보자.
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 중급 - 브루트 포스(문제) (0) | 2020.09.14 |
|---|---|
| 백준 알고리즘 중급 - 이분 탐색 (연습) (0) | 2020.09.07 |
| 백준 알고리즘 중급 - 이분 탐색 (0) | 2020.09.06 |
| 백준 알고리즘 중급 - 정렬 (0) | 2020.09.04 |
| 백준 알고리즘 중급 - 분할정복 (도전) (0) | 2020.09.02 |
