Problem Solving (98) 썸네일형 리스트형 백준 17955번 Max or Min 어제 처음으로 팀연습하다가 다이아 3을 풀어서 기쁜 마음에 풀이를 작성한다. 심지어 제출 한 번만에 맞췄다! 문제 요약 길이가 $N$인 원형 수열 $a$가 주어진다. $1 \le a_i \le M$ 이다. 이 때 다음과 같은 연산을 할 수 있다. $a_i$를 하나 골라서 인접한 두 수와 $a_i$의 최솟값 혹은 최댓값으로 $a_i$를 바꿔줄 수 있다. 이런 연산을 반복해서 수열 전체를 $k$로 만들기 위한 최소 연산 횟수를 계산해야 한다. $3 \le N \le 2 \cdot 10^5, 1 \le M \le 10^5$ 풀이 실제로 구해야 하는 것은 $1 \le k \le M$인 모든 $k$에 대한 답이지만 일단 이걸 $k$로 고정한 뒤에 최적의 연산 횟수를 구해보자. 일단 $k$가 존재하지 않는 수라면 .. 백준 21916번 Neo-Robin Hood 문제 요약 돈을 $m_i$달러만큼 들고 있는 정치가 $N$명이 주어진다. 각 정치가는 $p_i$만큼 돈을 원하고 있다. 이 때, 정치가들한테서 돈을 훔치려고 하는데 그냥 쌩으로 훔치면 위험하기 때문에 훔친사람의 수와 같은 수의 정치가들한테 그들이 원하는 만큼의 돈을 줘야 한다. 이 때, 돈을 훔칠 수 있는 정치가의 수의 최댓값을 구하시오. $ N \le 100,000$ $1 \le m_i, p_i \le 10^9$ 풀이 관찰 1 : 일단 돈을 줄 사람 $k$ 명을 정했다고 하자. 그렇게 되면 돈을 훔쳐야 될 사람 $k$ 명은 남은 사람 중에서 돈이 제일 많은 $k$ 명이 되는 것은 자명하다. 관찰 2. $k$ 명에게서 훔치는 것이 가능하다면 당연히 $k$ 명보다 적은 수의 정치가에게서 훔치는 것도 가능하.. Atcoder Begginer Contest 201 F가 꽤 어려운 라운드였던 거 같다. 그리고 D나 E는 꽤 전형적인 문제인데 모르면 처음에 떠올리기 어려운 문제들이다. 이해가 안되거나 설명이 부족하다 싶거나 잘못된 내용은 댓글로 말해주시면 감사하겠습니다. A - Tiny Arithmetic Sequence 만약에 세 숫자가 등차수열을 이룬다면 정렬했을 때 그 순서대로 공차가 같을 것이다. 이걸로 해결할 수 있다. #include using namespace std; int main() { vector v(3); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); if (v[1] - v[0] == v[2] - v[1]) cout v[i].second >> v[i].first; sort(.. 백준 15339번 Counting Cycles 문제 요약 정점이 $N$개 있고 간선이 $M$개인 연결그래프가 주어진다. 이 때, 단순 사이클의 갯수를 구해야 한다. $ 3 \le N \le 100000$, $ N-1 \le M \le N+15$ 풀이 제한이 10만이었구나 왜 20만으로 착각했을까 일단 간선의 제한이 매우 수상하다. $N+15$라는 저 어정쩡한 제한을 보라. 일단 간선이 $N-1$일 때는 트리다. 사이클이 존재하지 않는 그래프고, $N$개일 때는 당연히 사이클은 하나다. 트리에서 간선이 하나 추가될 때 마다 사이클이 생겨난다. 즉, 이렇게 해서 생길 수 있는 사이클은 최대 16개다. 여기서 중요한 사실이 있는데 생길 수 있는 사이클은 사이클끼리 겹치게 해서 홀수번만 겹쳐진 간선들을 사용하는 사이클 외에는 존재 할 수 없다. 는 강한 추.. Atcoder Beginner Contest 200 풀이 A, B, C는 정말 쉬운 편이고 D, E, F는 평균적인 라운드보다 좀 어렵게 뽑힌 거 같다. A - Century $x$가 주어지면 $ceil(x/100)$을 출력하면 된다. #include using namespace std; int main() { int x; cin >> x; cout N >> K; while(K--) { if(N%200 == 0) N /= 200; else N = N*1000 + 200; } cout N; long long ans = 0; for(int i=0;i> x; ans += cnt[x%200]; cnt[x%200]++; } cout N; for(int i=1;i> orig[i]; a[i] = orig[i] % 200; } ans[1][a[1]].push_back(1);.. 백준 18214번 Reordering the Documents 문제 요약 크기가 $N$인 문서 더미가 주어진다. 각 문서에는 $1$부터 $N$까지 수가 부여되어 있다. 문서 더미는 스택과 같은데 놓여있는 문서들의 순서는 뒤죽박죽이다. 이 때, 이 문서들을 다른 두 개의 임시 문서 더미로 옮긴 뒤에 정리하는 방식으로 문서 더미의 위에서부터 $1$부터 $N$까지로 차례대로 놓여있는 문서 더미를 만들려고 한다. 임시 문서 더미들은 최대 $M$의 높이를 가질 수 있다. 이 때, 서로 다른 두 개의 임시 문서 더미에 문서들을 놓는 경우의 수를 구하여라 . $ 1 \le N \le 5000$, $ N/2 \le M \le N$ 문제 요약이 잘 안된다. 링크 풀이 일단 처음의 문서 더미의 위에서부터 아래로 내려가는 순으로 문서들의 번호가 주어진다. 그리고 서로 다른 두 개의 스.. Atcoder Beginner Contest 189 풀이 F를 푼사람이 244명으로 F가 꽤 어려웠던 라운드같다. 아마 나도 문제에 쓰인 아이디어를 이 문제서 처음 봤다면 감도 안 왔을거 같다. E가 좀 수학적인 성향이 강한 느낌이다. 라운드 링크 A - Slot 정말 기본적인 문제. 길이 3인 문자열을 입력받고 세 글자가 전부 같은지 확인하자. 출력문이 Won, Lost로 좀 특이하니 주의 #include using namespace std; string s; int main() { cin >> s; if(s[0] == s[1] && s[1] == s[2]) cout X; X *= 100; int taken = 0; for (int i = 0; i > v >> p; int a = v * p; taken += a.. Atcoder Beginner Contest 190 풀이 Rated User 중에 올솔한 사람이 500명이나 되는 라운드였다. 아마 E, F가 전형적인 문제여서 그런 듯 하다. 라운드 링크 A - Very Very Primitive Game 일일이 시뮬레이션을 돌려도 되고 조건문 써서 수식으로 풀어도 된다. #include #include using namespace std; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int a, b, c; cin >> a >> b >> c; if(c == 0) { if(a > b) cout x >> y; if(x >= S || y M; for(int i=0;i> u >> v; cond.emplace_back(u, v); } cin >> K; for(int i=0.. 이전 1 2 3 4 ··· 13 다음