나그네

2638번: 치즈 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 공기에 두 면이 접촉해 있는 치즈는 사라진다. 발상이 중요한 문제로 치즈를 기준으로 탐색할지, 공기를 기준으로 탐색할지 기준을 잘 세워야 하는 문제다. 정답 풀이 이 문제에서 같은 시간에 사라지는 치즈가 모두 사라진 뒤 동시에 공기가 침투한다. 따라서 치즈가 사라지는 로직과 공기가 퍼지는 로직이 턴제로 진행되야 한다. 중요! 모눈종이의 맨 가장자리는 치즈가..

2143번: 두 배열의 합 문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 n과 m이 최대 1000이므로 가능한 모든 부분합을 구한 다음 가능한 조합의 수를 구하면 된다. 즉, A 부분합 배열의 각 원소에 대해 T가 되기 위해 필요한 수가 B 부분합 배열에 몇 개가 있는지 확인한다. B 부분합 배열을 오름차순 정렬한 후 lower_bound, upper_..

27920번: 카드 뒤집기 문제 https://www.acmicpc.net/problem/27920 27920번: 카드 뒤집기 $1$부터 $N$까지 서로 다른 정수가 적혀있는 카드를 $N$장 가지고 있다. 각 카드에는 앞면과 뒷면이 존재한다. 카드의 앞면에는 숫자가 적혀있고, 뒷면에는 카드의 무늬가 그려져 있다. $N$장의 카 www.acmicpc.net 풀이 카드를 어떻게 해야 조건을 만족하며 모두 뒤집을 수 있을지 구성하는 문제다. 처음부터 든 생각은 N은 마지막에 배치해야 하기 때문에 양쪽 끝부터 수를 줄여가며 구성하면 될 것 같았다. 노트에 한 번 적어보고 바로 구현해서 풀었다. 예를 들어 N이 4인 경우 카드 배치는 3 1 4 2, 순서는 1 4 2 3으로 하면 가능하다. N이 5인 경우엔 4 ..

27919번: UDPC 파티 문제 https://www.acmicpc.net/problem/27919 27919번: UDPC 파티 첫 번째 줄에 참가자가 투표한 결과 $V$가 주어진다. $V$는 U, D, P, C만 포함하는 문자열이고, 길이는 $0$보다 크고 $100\ 000$을 넘지 않는다. www.acmicpc.net 풀이 U와 C, D와 P를 같은 문자로 생각하고 개수를 센다. D와 P는 둘 다 선정되거나 둘 다 선정되지 않을 수 밖에 없다. U와 C의 수를 UC, D와 P의 수를 DP라고 할 때 U가 선정되기 위해서는 UC의 수가 (DP의 수 + 1) / 2보다 커야한다. 이유는 UC가 2, DP가 4일 때 DP를 2, 2로 나누어도 U가 각각보다 크지 못하므로 U가 선정될 수 없다. 그리고 D..

27918번: 탁구 경기 문제 https://www.acmicpc.net/problem/27918 27918번: 탁구 경기 달구와 포닉스는 탁구 치는 것을 좋아한다. 윤이는 오늘도 탁구를 치는 달구와 포닉스를 보고, 누가 경기에서 승리할지 예측해 보기로 했다. 달구와 포닉스가 탁구 경기를 진행하는 규칙은 다음 www.acmicpc.net 풀이 경기 결과에 따라 팀의 점수를 증가시키다가 차이가 2가 되는 순간 멈추고 각 팀의 점수를 출력하는 문제다. 반복문 제어를 할 수 있는지 여부를 분별하는 문제. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, a = 0, b = 0; cin >..

Round #860 (Div. 2) 대회 https://codeforces.com/contest/1798 Dashboard - Codeforces Round 860 (Div. 2) - Codeforces codeforces.com 푼 문제 A. Showstopper 길이가 같은 배열 a와 b의 마지막 원소는 각 배열에서의 최댓값이어야 한다. 이때 배열 a, b에서 같은 인덱스에 위치한 원소는 서로 바꿀 수 있다. 이때 위 조건을 만족시킬 수 있는지 여부를 구하는 문제다. 먼저 배열 a에서 마지막 원소보다 큰 다른 원소가 있으면 배열 b의 원소와 swap 했다. 그런 다음 배열 a, b가 모두 조건을 만족하면 YES를 출력하고 만족하지 않으면 배열 b를 기준으로 다시 한번 진행한 다음 조건을 만족하면 YE..

27889번: 특별한 학교 이름 문제 https://www.acmicpc.net/problem/27889 27889번: 특별한 학교 이름 GEC에는 여러 학교가 있다. 각 학교의 약칭과 정식 명칭은 다음과 같다. NLCS: North London Collegiate School BHA: Branksome Hall Asia KIS: Korea International School SJA: St. Johnsbury Academy 학교 이름을 좋아하는 규빈이 www.acmicpc.net 풀이 문제에 주어진 약칭을 각각 조건문에 넣어 정식 명칭을 출력하도록 하면 되는 문제다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); c..

13975번: 파일 합치기 3 문제 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 풀이 두 개의 파일을 합치는데 드는 비용은 두 파일의 크기의 합이다. 합친 파일을 다른 파일과 또 합칠 수 있고 하나의 파일을 만들기 위해 필요한 비용의 최솟값을 구하는 문제다. 각 파일의 크기가 최대 10,000이고 파일의 수가 최대 1,000,000 이므로 long long 자료형을 사용해야 한다. 작은 두 파일을 합치면 비용이 적게 들고 그 파일을 합칠..

17425번: 약수의 합 문제 https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 예전에 모든 수의 약수의 합을 에라토스테네스의 체를 사용해 구하는 법을 9213번 문제를 통해 만들어봤다. [9213 꽤 좋은 수 해설] 링크를 참고해 주길. 어떤 수 A은 A의 배수의 약수다. 범위 내 모든 A의 배수에 A을 더해준다. 그러면 sieve의 A번 인덱스에는 A의 모든 약수의 합을 값으로 가..

1197번: 최소 스패닝 트리 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 신장 트리(Minimun Spanning Tree, MST)의 개념을 알고 있으면 풀 수 있는 standard 문제다. 최소 스패닝 트리는 주어진 정점을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소가 되는 트리다. 우선순위 큐를 사용하는 프림 알고리즘과 크루스칼 알고리즘으로 구현한 MST 알고리즘을..