백준_문제 풀이 및 해설
-
BOJ (브론즈)
[백준/알고리즘] 19532번 수학은 비대면강의입니다 (브론즈 3)
BOJ 19532번 풀이 알고리즘 : 수학, 완전탐색 UCPC 2020 예선 A번 문제인 수학은 비대면강의입니다 문제입니다. 대회때는 구현속도가 빠른 친구가 풀어서, 어떤 문제인지 제대로 보지도 못했는데, 간단한 완전탐색으로 해결했습니다. 문제에서 x, y가 -999 이상 999 이하의 정수로 주어진다고 했으므로, x의 값을 해당 범위로 완전탐색하고, 그때 valid한 y값이 존재한다면 정답이므로 출력 후 루프를 빠져나갑니다. 간단하게 첫째식에 x값을 넣어서 계산한 y값과 둘째식에 x값을 넣어서 계산한 y값이 같다면 출력하게 만들었습니다. 아래는 제출코드입니다. 더보기 #include // 2의 제곱수 판정 #define POW2(X) (X) == ((X)&(-(X))) // int pair 간단히 #d..
-
BOJ (실버)
[백준/알고리즘] 19539번 사과나무 (실버 1)
BOJ 19539번 풀이 알고리즘 : 그리디 알고리즘, 수학 UCPC 2020 예선 H번 문제인 사과나무 문제입니다. 대회 당시에는 해결방법이 정말 안보여서 꽤 어려웠던 문제인데, 다시 풀어보니 어렵지 않은 문제입니다. 먼저 물을 1회 뿌릴 때 마다 나무의 성장을 1, 2를 각 1회씩 시킬 수 있습니다. 즉, 한번에 성장시킬 수 있는 총 높이는 3입니다. 그래서 목표한 모든 나무의 높이의 합이 3의 배수가 아니라면 항상 "NO" 입니다. 만약 높이의 합이 3의 배수라면, 다음과 같이 생각할 수 있습니다. 총 X번 물을 뿌렸으면, 1만큼 성장을 X번, 2만큼 성장을 X번 한 것입니다. 즉, 높이의 합이 3의 배수이면서, 2만큼 성장을 X번 시킬 수 있다면 "YES"입니다. 왜냐하면 2만큼 성장을 X번 시켰..
-
BOJ (골드)
[백준/알고리즘] 19541번 루머 (골드 4)
BOJ 19541번 풀이 알고리즘 : BFS UCPC 2020 예선 G번 문제인 루머 문제입니다. 한 노드를 봤을 때, 연결된 인접 노드의 절반 이상이 루머를 믿고있다면, 해당 노드도 루머를 믿게 되고, 노드별로 루머를 믿게 된 시간을 출력하는 문제입니다. 여러가지 방법이 있겠지만, 저는 Queue를 두개 이용하여 BFS를 통해 해결했습니다. queue q, qq로 선언을 하였고, 다음과 같이 사용하였습니다. q : "루머를 믿고 있는" 노드번호, 현재 시간을 저장 qq : "q에서의 노드에 인접한" 노드번호, 현재 시간을 저장 먼저 q에 최초 루머를 믿고 있는 노드번호와 시간 0을 입력합니다. while(!q.empty()) 안에는 두개의 while문이 있는데, 첫번째 while문에서는, 현재 q에 들..
코드포스_대회 후기 및 풀이
-
Code Forces (Div. 3)
[코드포스/Contest] Codeforces Round #653 (Div. 3), A ~ D
#653 후기 문제 A ~ C는 쉬웠던 것 같고, D번이 어떻게 풀어야할지 감도 안잡혀서 오래걸렸던 대회였다. DIV3 대회여서 그런지 딱 실력만큼 푼 것 같다. #653 문제 A번 Required Remainder - 성공 더보기 정수 x, y, n이 주어진다. 0 x >> y >> n; int m = (n - y) / x; cout tc; while(tc--) { int n; cin >> n; if(n == 1) { cout s; for(int i = 0; i < n / 2; i++) { if(s[i] == '(') stkl.push(true); else if(s[i] == ')') { if(stkl.empty()) { cntl++; } else { stkl.pop(); } } } for(int i ..
-
개별문제풀이
[코드포스/개별문제] CF#623 C번 Restoring Permutation
코드포스 #623 C번 - Restoring Permutation 1부터 2n까지의 정수를 각각 하나씩 가지고 있는 정수 배열 a가 있다. 배열 b는 b[i] = min(a[2i - 1], a[2i])로 정의된다. 배열 b가 주어졌을 때, 배열 a를 출력하시오. 1, 2, ..., 2n의 정수가 각각 사용 되었는지 확인하고, 입력받은 배열 b의 원소에 대해서, 가장 가까운 큰 수(b + 1, b + 2, ...)를 확인한다. 만약 현재 값보다 큰 값이 없으면 b[i]를 정의할 수 없기 때문에 불가능한 경우이고, 만약 가능하다면 해당 값을 체크처리하고 출력한다. 아래는 제출코드이다. #include // 2의 제곱수 판정 #define POW2(X) (X) == ((X)&(-(X))) // 기본설정 typ..
-
개별문제풀이
[코드포스/개별문제] CF#623 B번 Homecoming
코드포스 #623 B번 - Homecoming 집에 가기 위한 길이 있다. 길은 걸어가거나, 버스 또는 전차를 타고 이동할 수 있다. 입력으로 교차로의 상태가 주어지는데, A는 버스로, B는 전차로 이동할 수 있는 길이고, 버스와 전차는 서로 갈아탈 수 있다. 각각의 티켓은 가격을 지불해야 하고, 현재 가지고 있는 돈이 주어진다. Petya가 현재 가진 돈으로 집으로 돌아가기 위해 걸어가야 하는 최소 거리를 구하시오. 간단한 이분탐색 문제이다. 걸어가서 처음 탑승하는 정류장의 위치를 이분탐색을 통해 검색한다. 각각의 탐색에서 집으로 가기위한 티켓의 총 비용을 계산한다. 만약 돈이 부족하다면 더 많이 걸어가야 하고, 돈이 충분하다면, 최소 거리가 있을 수 있으므로 더 가까운 거리에서 탐색한다. 아래는 제출..
