개발/알고리즘
[Codeforce] Educational Codeforces Round 115 (Rated for Div. 2) 풀이
라사 RASA
2022. 7. 2. 19:17
A : Computer Game (0:19)
(0,0) 위치에서 (1,n) 까지 갈 수 있는지 확인하는 문제이다. 오랜만에 알고리즘 문제를 풀어서 Virtual participation(이하 VP) 당시 얼탔다. 그냥 느낌대로 풀었는데 시간도 20분 가까이 걸렸고, 코드도 안 예쁘다. 어차피 오른쪽 아래로만 가니 8방위가 아니라 오른쪽 위, 오른쪽 아래, 아래, 이렇게 3 방향만 고려하면 됐다. 다음에는 예쁘게 풀어보자.
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
vector<vector<int>> field;
vector<vector<bool>> visited;
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { 1,1,0,-1,-1,-1,0,1 };
0
int main(void)
{
int T, n;
string input;
cin >> T;
while (T--)
{
cin >> n;
field.assign(2, vector<int>(n+1, 1));
visited.assign(2, vector<bool>(n + 1, false));
for (int i = 0; i < 2; ++i)
{
input = "";
cin >> input;
for (int j = 0; j<input.size(); ++j)
{
field[i][j] = input[j] -'0';
}
}
queue<pair<int, int>> bfs;
bfs.push({ 0,0 });
while (!bfs.empty())
{
int y = bfs.front().first;
int x = bfs.front().second;
if (y == 1 && x == n-1)
break;
bfs.pop();
for (int i = 0; i < 8; ++i)
{
if (y + dy[i] < 0 || y + dy[i] >1 || x + dx[i] < 0 || x + dx[i] == n)
continue;
if (field[y + dy[i]][x + dx[i]] == 0)
{
if (visited[y + dy[i]][x + dx[i]])
continue;
bfs.push({ y + dy[i], x + dx[i] });
visited[y + dy[i]] [x + dx[i]] = true;
}
}
}
if (bfs.empty())
cout << "NO\n";
else
cout << "YES\n";
}
}
아래는 같이 스터디를 하는 기만러 Dreamw 님의 코드인데 허락을 구하고 글에 첨부했다. 오른쪽 부분이 아예 막혀있는지 확인하는 코드인데 나랑은 다르게 짧고 예쁘게 짠 걸 확인할 수 있다.
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100001
#define INF 1e9+7
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define ll long long
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt;
cin >> tt;
while(tt--){
int n, flag=0; cin >> n;
string s1, s2; cin >> s1 >> s2;
for(int i=1; i<n; i++){
if(s1[i]-48 && s2[i]-48){
flag=1;
break;
}
}
cout << (flag?"NO":"YES") << endl;
}
return 0;
}
B : Groups (0:43 - 대회 끝나고 5분 뒤에 AC 받음 ㅠㅡㅠ)
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t, n, input;
bool flag;
vector<int> student;
vector<int> day_count;
cin >> t;
while (t--)
{
flag = false;
cin >> n;
if (n % 2 == 1)
{
cout << "NO\n";
continue;
}
student.assign(n, 0);
day_count.assign(5, 0);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 5; ++j)
{
cin >> input;
if (input == 1)
{
++day_count[j];
student[i] += 1 << j;
}
}
}
for (int i = 0; i < 5 && !flag; ++i)
{
if (day_count[i] >= n / 2)
{
vector<int> count(5, 0);
vector<int> both(5, 0);
for (int j = 0; j < 5 && !flag; ++j)
{
if (i == j)
continue;
for (int k = 0; k < student.size(); ++k)
{
if ((student[k] & 1 << j) == 1 << j)
{
if ((student[k] & 1 << i) == 0)
++count[j];
else if ((student[k] & 1 << i) == 1 << i)
++both[j];
}
}
}
for (int j = 0; j < 5 && !flag; ++j)
{
if (i == j)
continue;
int supplement = n / 2 - count[j];
if (count[j] >= n / 2)
flag = true;
else if (both[j] >= supplement && day_count[i] - n / 2 >= supplement)
flag = true;
}
}
}
if (flag)
cout << "YES\n";
else
cout << "NO\n";
}
}
아래는 마찬가지로 같이 스터디를 하는 기만러 Dreamw 님의 코드인데 허락을 구하고 글에 첨부했다. 나와는 달리 조건이 깔끔하다. i 번 요일과 j 번 요일이 모두 안 되는 학생이 있다면 건너뛰고, 하나라도 된다면 각각 cnt1, cnt2 에 1을 더해서 가능한 학생 수를 집계한다. 이렇게 집계된 값이 둘 다 n/2 보다 크거나 같다면 가능하다고 판단하여 "YES"를 출력한다.
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100001
#define INF 1e9+7
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define ll long long
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt;
cin >> tt;
while(tt--){
int n; cin >> n;
bool arr[1001][5]={0};
for(int i=0; i<n; i++){
for(int j=0; j<5; j++) cin >> arr[i][j];
}
int cflag=0;
for(int i=0; i<4; i++){
for(int j=i+1; j<5; j++){
int cnt1=0, cnt2=0, flag=0;
for(int k=0; k<n; k++){
if(!arr[k][i] && !arr[k][j]){
flag=1; break;
}
if(arr[k][i]) cnt1++;
if(arr[k][j]) cnt2++;
}
if(flag) continue;
if(cnt1>=n/2 && cnt2>=n/2){
cflag=1;
break;
}
}
}
cout << (cflag?"YES":"NO") << endl;
}
return 0;
}
비고
Tistory로 블로그 이전하면서 글들을 보기 좋게 정리하고 있는데 B번까지만 정리하고 게시한 글인 것 같다.