서론(잡소리)
2년만에, Atcoder Contest에 참가해봤습니다.
2년전에 딱 한번 해보고, 안했는데 알고리즘 동아리에 Atcoder 대회일정이 올라왔길래 참가해봤습니다..ㅋㅋㅋ
일단, 전체적으로 문제가 되게 짧았습니다. 그래서 영어 해석에 시달리진 않았는데... 수학으로 접근해야 하는 문제가 있어서 저는 개인적으로 힘들었습니다. (이걸 더 좋아하시는 분들도 있긴 하지만..)
아무튼, 저는 E번을 제외하고 AC를 받았고, E는 에디토리얼을 봐도 이해가 안가서, 풀이를 적지 못했습니다.
A - Lucky7
바로 보자마자 코드를 작성하고 제출했습니다.
굳이 다른 설명 필요없을 것 같습니다.
a = input()
if '7' in a:
print("Yes")
else:
print("No")
B - FizzBuzz Sum
O(n) 풀이로 그냥 한번 탐색하면서 3 혹은 5로 나누어떨어지지 않으면 ans에 누적하면 됩니다.
n = int(input())
s = 0
for i in range(1,n+1):
if i%3 !=0 and i%5 !=0:
s += i
print(s)
C - Sum of gcd of Tuples (Easy)
일단 a와 b의 최대공약수를 구하는 수식을 gcd(a,b)라고 하겠습니다.
a, b, c 세 수의 최대 공약수를 구할 때는 gcd(a,b,c) == gcd(gcd(a,b),c) == gcd(a,gcd(b,c)) == gcd(b, gcd(a,c)) 이므로, 차례대로 원하는대로 숫자를 넣으면 됩니다. 그리고 하나 더, gcd(a,b)는 당연하게도 a와 b보다 작거나 같겠죠?\
코드에서는 D라는 배열에 D[a][b] = gcd(a,b) 식으로 값들을 넣어놨습니다.
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b>0?gcd(b,a%b):a;
}
int D[220][220];
int N,ans;
int main() {
cin >> N;
for(int x=1; x<=N; x++) {
for(int y=x; y<=N; y++) {
int ret = gcd(x,y);
D[x][y] = ret;
D[y][x] = ret;
}
}
for(int x=1; x<=N; x++) {
for(int y=1; y<=N; y++) {
for(int z=1; z<=N; z++) {
ans += D[D[x][y]][z];
}
}
}
cout<<ans;
}
D - RGB Triplets
이 문제는 조금 꼼수를 부렸습니다.( 더 쉬운 풀이가 있을 것 같긴 합니다.)
먼저 코드부터 보겠습니다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N,cnt,ans;
string s;
vector <ll> V1;
vector <ll> V2;
int main() {
cin >> N >> s;
for(int x=0; x<N; x++) {
if(s[x] == 'R') V1.push_back(x);
if(s[x] == 'G') V2.push_back(x);
if(s[x] == 'B') cnt++;
}
for(auto i : V1) {
for(auto j : V2) {
ll mi = 0;
ll diff = (j-i) > 0 ? (j-i) : (i-j);
if(i < j) {
if(j+diff < N && s[j+diff] == 'B') mi++;
if(i-diff >=0 && s[i-diff] == 'B') mi++;
if(diff % 2 == 0) {
if(s[i + diff/2] == 'B') mi++;
}
}
else {
if(i+diff < N && s[i+diff] == 'B') mi++;
if(j-diff >=0 && s[j-diff] == 'B') mi++;
if(diff % 2 == 0) {
if(s[j + diff/2] == 'B') mi++;
}
}
ans += cnt - mi;
}
}
cout<<ans;
}일단, R과 G의 index를 각각 V1과 V2에 넣어주었고, B는 개수만 세주었습니다.
이제, R과 G를 하나하나 짝지읍니다. 그때, B가 있으면 안되는 자리(차이가 동일해지는 자리)에 B가 있으면 따로 count해주고, count 해준만큼을 전체 B의 개수에서 빼준뒤 ans에 더해줍니다.
어찌됬든간에, RG가 짝이 지어있다면, B를 짝 지어야 하는 상황이고, B만 R과 G 사이의 차이와 동일하게 차이를 만드는 위치에만 안오면 되기 때문입니다.
E - Sum of gcd of Tuples (Hard)
FAIL모르겠어요..모르겠다구요..
에디토리얼봐도 이해가 아직 안가요..
F - Select Half
대회에서는, 제가 절대값 기호를 못보고 풀어서 뻘짓을 좀 했습니다..
아무튼 이 문제의 핵심은 숫자들을 선택할 때, 몇 개를 건너뛸 수 있느냐 입니다.
일단 2가지 경우로 나뉩니다.
i) 주어지는 수가 짝수인 경우
ii) 주어지는 수가 홀수인 경우
먼저 짝수인경우부터 보겠습니다.
예를 들어 8개의 숫자가 주어졌다고 합시다.
그러면 4개의 숫자를 선택해야하고, 숫자 사이마다 적어도 1칸씩 총 3개의 숫자는 배제되어야 합니다.
그리고 나머지 1개의 숫자는 어쩔 수 없이 배제되어야 하죠.
이처럼, 짝수일때는 무조건 1개 더 배제해야 합니다.
한번, 홀수인 경우를 보겠습니다.
예를 들어 7개의 숫자가 주어졌다면 3개의 숫자를 선택해야 하고, 앞서 짝수처럼 사이에 2개의 숫자가 배제되어야 합니다. 그러면 홀수인경우에는 2개의 숫자를 배제해야 한다는 것이죠.
그러면. n개의 숫자중에 [n/2]의 숫자를 띄엄띄엄 선택할 때, 굳이 띄지 않아도 되는 곳을 띄운 횟수를 카운트하면 될 것 같네요. (최대 2니까요)
이를 DP 배열로 만들자면,
D[i][j]: i번째 숫자를 선택하려할때, 지금까지 굳이 띄우지 않아도 되는 곳을 띄운 횟수가 j인 경우에 선택한 숫자들의 합 중 최대값
이것을 생각하고, 저는 BFS를 짰고, 코드는 조금 복잡합니다..
짝수일때, 홀수일때를 구분하고 난 뒤에 BFS를 작성했습니다. 판별해야할 조건이 다르다고 생각하기 때문입니다.
#include <iostream>
#include <queue>
#define MX 999999999999999
using namespace std;
typedef long long ll;
ll N;
ll ar[440000];
ll D[440000][11];
struct st {
ll point, cnt, S;
};
int main() {
cin >> N;
for(int x=0; x<N; x++) {
cin >> ar[x];
for(int d=0;d<4; d++) {
D[x][d] = -MX;
}
}
queue <st> Q;
bool chk = true;
ll ans = 0;
if(N%2 ==0) {
Q.push({0,0,ar[0]});
Q.push({1,1,ar[1]});
while(!Q.empty()) {
st F = Q.front();
Q.pop();
if(F.point >= N) continue;
if(D[F.point][F.cnt] > F.S) continue;
D[F.point][F.cnt] = F.S;
if(F.point == N-1 && F.cnt == 1) {
if(chk) {
ans = F.S;
chk = false;
}
if(F.S > ans ) {
ans = F.S;
}
}
if(F.point == N-2 && F.cnt == 0) {
if(chk) {
ans = F.S;
chk = false;
}
if(F.S > ans) {
ans = F.S;
}
}
if(F.cnt == 0) {
Q.push({F.point+3, F.cnt + 1, F.S + ar[F.point+3]});
}
Q.push({F.point+2, F.cnt, F.S + ar[F.point+2]});
}
cout<<ans;
}
else {
Q.push({0,0,ar[0]});
Q.push({1,1,ar[1]});
Q.push({2,0,ar[0]+ar[2]});
Q.push({2,2,ar[2]});
while(!Q.empty()) {
st F = Q.front();
Q.pop();
if(F.point >= N) continue;
if(D[F.point][F.cnt] > F.S) continue;
D[F.point][F.cnt] = F.S;
if(F.point == N-1 && F.cnt ==2) {
if(chk) {
ans = F.S;
chk = false;
}
if(F.S > ans) {
ans = F.S;
}
}
if(F.point == N-2 && F.cnt == 1) {
if(chk) {
ans = F.S;
chk = false;
}
if(F.S > ans) {
ans = F.S;
}
}
if(F.point == N-3 && F.cnt == 0) {
if(chk) {
ans = F.S;
chk = false;
}
if(F.S > ans) {
ans = F.S;
}
}
if(F.cnt == 0 || F.cnt == 1) {
Q.push({F.point+3, F.cnt + 1, F.S + ar[F.point+3]});
}
Q.push({F.point+2, F.cnt, F.S + ar[F.point+2]});
}
cout<<ans;
}
}
아무튼, 이정도면 된 것 같습니다.
질문이나 궁금하신 점은 댓글로 달아주세요.
Rmx