#648 후기
|
A부터 C번까지는 구현보다는 아이디어를 떠올리는게 중요했다고 생각이 드는데, 내가 이런 부분에서 약점을 가지고 있다는 것을 다시 알게 되었고, D번도 다른 방법이 있을 수 있겠지만, 구현능력이 좋았다면 풀 수 있었지 않았을까 하는 생각이 드는 내 한계를 느낀 아쉬운 대회였다. |
#648 문제
A번 Matrix Game - 성공
n * m 크기의 행렬이 있다. 행렬은 0 또는 1로 초기화 할 수 있다. matrix[i][j] == 1 이란 뜻은 해당 행렬에 i번째 가로줄과 j번째 세로줄에는 다른 1인 값이 들어올 수 없다는 것을 의미한다. Matrix Game은 Ashish와 Vivek이 서로 한 번 씩 행렬을 1로 바꿀 수 있을 때, 더이상 바꿀 수 없는 사람이 지는 게임이다. 행렬이 주어졌을 때, 이기는 사람을 출력하시오.
단순히 문제에서 나온대로 구현하면 되는 문제이다.
나는 배열의 크기를 각각 (n + 1) * (m + 1)로 초기화 하고,
입력을 받을 때, block[i][0]과 block[0][j]에 각각 해당 가로, 세로줄의 사용 여부를 저장했다.
그리고 배열을 순회하면서, 가로와 세로 줄 모두 사용할 수 있으면, 해당 위치를 1로 바꾸고, 가로/세로줄을 사용하지 못하게 바꾸면서 누가 이겼는지 확인하였다.
정답 코드 보기
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int tc;
cin >> tc;
while(tc--) {
int n, m;
bool turn = true;
cin >> n >> m;
int block[50 + 1][50 + 1] = {0};
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> block[i][j];
if(block[i][j] == 1) {
block[i][0] = 1;
block[0][j] = 1;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(block[i][0] == 1 || block[0][j] == 1) continue;
else {
block[i][j] = 1;
block[0][j] = 1;
block[i][0] = 1;
turn = !turn;
}
}
}
if(turn) {
cout << "Vivek";
} else {
cout << "Ashish";
}
cout << "\n";
}
return 0;
}B번 Trouble Sort - 성공
두개의 값을 인자로 가지는 배열이 있다. 첫번째 값은 Value로, 정수 값이 주어진다. 두번째 값은 Type으로, 0과 1의 두가지로 주어진다. Type이 서로 다른 경우, 서로 자리를 바꿀 수 있다.
배열이 주어졌을 때, 해당 배열을 감소하지 않는 배열로 바꿀 수 있는지 출력하시오.
처음에 하나하나 다 해봐야하나 고민하다가, 한가지 특징을 발견하였다. 바로
배열에 Type이 0과 1 모두 존재한다면, 감소하지 않는 배열로 만들 수 있다는 것이다.
즉, Type이 1인 원소 하나와, Type이 0인 원소 나머지가 있으면, 1의 자리를 옮기면서 배열을 정렬할 수 있다.
그럼 다음으로 생각해야 할 것은, 둘 중에 하나라도 없을 경우이다.
하나라도 없을 경우, 기본 배열이 감소하지 않는다면 변화시키지 않아도 YES이고, 그렇지 않다면 NO이다.
정답 코드 보기
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int tc;
cin >> tc;
while(tc--) {
int n, temp, zero = 0, one = 0, prev = 0;
bool ans = true;
cin >> n;
vector<int> a;
for(int i = 0; i < n; i++) {
cin >> temp;
a.push_back(temp);
if(prev == 0) prev = temp;
else {
if(prev <= temp) {
continue;
} else {
ans = false;
}
}
}
for(int i = 0; i < n; i++) {
cin >> temp;
if(temp == 1) one++;
else zero++;
}
if(one * zero == 0) {
if(ans) cout << "YES\n";
else cout << "NO\n";
} else {
cout << "YES\n";
}
}
return 0;
}C번 Rotation Matching - 성공
길이가 n이고, 각각의 원소는 1 ~ n인, 동일한 두 정수 배열 a, b가 주어진다.
a와 b의 각 원소에 대해서, 위치(index)와 값이 서로 같으면 두 페어는 매치된다고 본다.
두 배열을 서로 왼쪽 또는 오른쪽으로 밀 수 있을때, 최대로 매치되는 원소의 개수를 출력하시오.
문제를 다음과 같이 접근했다.
배열 a의 원소 a[i]와 배열 b의 원소 b[j]가 같다고 가정하면, 1 ~ n까지의 각각의 원소에 대해서,
b의 인덱스 j를 a의 인덱스 i로 바꾸기 위한 미는 횟수를 구해서 배열에 저장한다.
문제의 예제로 예를 들어 설명하면,
배열 b [2, 3, 4, 5, 1]에서 2를 a의 2의 위치로 이동시키기 위해서는 오른쪽으로 1번, 3을 a의 3의 위치로 이동시키기 위해서는 오른쪽으로 한번 , ... 이렇게 동일하게 진행해서,
오른쪽으로 한번 움직이면 5개의 원소를 일치시킬 수 있다고 볼 수 있다.
이와 같이 코드에서 각각의 원소에서 몇 번 움직여야 일치되는지 확인한 후, 마지막에 가장 많이 일치시킬 수 있는지 확인해서 출력해주었다.
정답 코드 보기
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, cnt = 0, val;
cin >> n;
int ans[n + 1]; // ans[x] : x번 움직였을 때, 일치하는 개수
int a[n] = {0}; // a[x] == 1 : x라는 숫자가 1번째 index에 있음
for(int i = 0; i < n; i++) {
cin >> val;
a[val] = i;
}
memset(ans, 0, sizeof(ans));
for(int i = 0; i < n; i++) {
cin >> val;
// cout << ans[i] << " " << i <<"\n";
if(i == a[val]) {
ans[0]++;
} else if(i < a[val]) {
// a에서 현재 bi의 값이 더 오른쪽에 있을 경우
ans[a[val] - i]++;
} else {
// 더 왼쪽에 있을 경우
int idx = n - i + a[val];
ans[idx]++;
}
}
int maxnum = 0;
for(int i = 0; i <= n; i++) {
if(maxnum < ans[i]) maxnum = ans[i];
}
cout << maxnum;
return 0;
}D번 Solve The Maze - 실패
n * m 크기의 미로가 주어진다. 배열의 원소로는 빈 공간('.'), 벽('#'), 좋은사람('G'), 나쁜사람('B') 이 주어진다.
미로에서 탈출하는 유일한 방법은, (n, m) 좌표로 이동해서 탈출하는 것이다.
하지만 조건이 있다. G는 항상 탈출해야만 하고, B는 탈출해서는 안된다. 이를 위해, 원하는 위치에 벽('#')을 설치할 수 있다. 조건에 부합하여, G만이 탈출할 수 있는지를 출력하시오.
(대회중에는 구현하다가 시간이 부족해서 포기했는데, 다시 풀어서 성공하였다.)
접근 방법은 간단하다.
만약 미로에 G가 없으면, 모든 G가 탈출한것이므로, YES이다.
그렇지 않다면, B를 확인해서, B의 상/하/좌/우에 벽을 설치한다. 설치하는 중에, B와 G가 인접한것이 있다면, G가 탈출할 경우, B도 항상 탈출할 수 있기 때문에 NO이다.
또한 벽을 모두 설치한 이후에, 탈출구에 벽이 있다면 NO이다.
마지막으로, 탈출구에서부터 DFS나 BFS를 이용하여, 이동할 수 있는 모든 공간을 탐색한 뒤, 마지막에 미로에서 모든 G가 탈출구로 탈출할 수 있는지 확인해서 탈출할 수 있는 경우만 YES이다.
방법은 간단하지만, 구현 능력이 부족해서 코드가 굉장히 길고 더럽게 구현되었다..
다음은 정답 코드이다.
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
// 전역변수
int n, m; // 배열의 크기
vector<string> board(50 + 1);
// 배열 안에 위치할 수 있는지 리턴
bool inRange(int y, int x) {
return (0 <= y && y < n && 0 <= x && x < m);
}
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int tc;
cin >> tc;
while(tc--) {
// 초기화
cin >> n >> m;
int gcnt = 0, bcnt = 0;
stack< pair<int,int> > bs;
for(int i = 0; i < n; i++) {
cin >> board[i];
for(int j = 0; j < m; j++) {
if(board[i][j] == 'G') gcnt++;
else if(board[i][j] == 'B') {
bs.push(make_pair(i,j));
bcnt++;
}
}
}
if(gcnt == 0) {
// G가 없는경우 항상 가능
cout << "YES\n";
} else {
bool ret = true;
if(0 < bcnt && ret) {
// B가 있는 경우, B의 주변을 벽으로 막음
while(!bs.empty()) {
int x = bs.top().second;
int y = bs.top().first;
bs.pop();
for(int i = 0; i < 4; i++) {
int xx = x + dirx[i];
int yy = y + diry[i];
if(inRange(yy, xx)) {
if(board[yy][xx] == '.') {
board[yy][xx] = '#';
} else if(board[yy][xx] == 'G') {
ret = false;
} else {
continue;
}
}
}
}
}
if(!ret || board[n - 1][m - 1] == '#') {
// B를 벽으로 막을 수 없어서 불가능
cout << "NO\n";
} else {
// G가 (n - 1), (m - 1) 로 이동가능한지 확인
bool check[50 + 1][50 + 1] = {0};
bool canmove[50 + 1][50 + 1] = {0};
stack< pair<int,int> > solve;
solve.push(make_pair(n - 1, m - 1));
while(!solve.empty()) {
int x = solve.top().second;
int y = solve.top().first;
solve.pop();
check[y][x] = true;
if(board[y][x] == '#' || board[y][x] == 'B') {
canmove[y][x] = false;
continue;
}
for(int i = 0; i < 4; i++) {
int xx = x + dirx[i];
int yy = y + diry[i];
if(inRange(yy, xx)) {
if(!check[yy][xx] && (board[yy][xx] == '.' || board[yy][xx] == 'G')) {
solve.push(make_pair(yy, xx));
canmove[yy][xx] = true;
} else{
continue;
}
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(board[i][j] == 'G') {
ret = ret && canmove[i][j];
}
}
}
if(ret) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
}
return 0;
}
'코드포스_Code Forces > Code Forces (Div. 2)' 카테고리의 다른 글
| [코드포스/Contest] Codeforces Rounde #651 (Div. 2), A ~ C (0) | 2020.06.23 |
|---|---|
| [코드포스/Contest] Codeforces Round #647 (Div. 2) (0) | 2020.06.05 |
| [코드포스/Virtual] Codeforces Round #620 (Div. 2) (0) | 2020.05.30 |
