2021 ICPC Sinchon Summer Algorithm Camp Contest - 초급
대회 있는지도 모르고 참여 안했었는데, Diboongi팀 연습용으로 그날 저녁에 진행했었다. 구현 연습용이었으므로, 1시간 30분 시간제한을 두고 바로 시작했다. 4(D)번은 솔루션 생각해서 코드 짜놓고 틀려서 왠가 싶었는데 끝난 직후에 이진탐색을 이상하게 했던게 문제였다. 바로 AC 6(F), 7(G)번은 사실 천천히 봤으면 확실히 풀만한 문제였긴한데, 시간이 부족했다 ㅠ A. 이진수 나눗셈 1) 오른쪽에서 연속된 0의 개수가 m보다 크다면 나누어떨어지고, 아니면 나누어떨어지지 않는다고 생각했다. #include using namespace std; int n, m, i; char s[1100000]; int main(){ scanf("%d\n%s\n%d",&n,s,&m); for(i=n-1; i>=0..
[백준] GCD 곱
문제 : https://www.acmicpc.net/problem/14860 문제요약 : GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구해라 조건 : 1. 1 ≤ N, M ≤ 15,000,000 해설 : i) Naive Solution 각각의 i(1 ≤ i ≤ N), j(1 ≤ j ≤ M)에 대해 GCD(i, j)를 구해 곱하면서 O(NM)으로 구할 수 있겠죠? -> 15000000^2이므로 너무 느립니다 ii) 조금더 빠르게 N=8, M=8이라 합시다. GCD(i,j)들 중에 2의 인수가 얼마 있는지 알아봅시다. 1..
[백준] 2561번 세 번 뒤집기
문제 : https://www.acmicpc.net/problem/2561 문제요약 : 수열의 구간 (xi,yi)를 순차적으로 뒤집어 원래 수열로 만들 때, xi,yi(i=1~3) 를 출력하라 조건 : 1. 정수 N (5≤N≤1000) 2. 구간[i,i]를 뒤집으면 아무런 변화가 없는데 이러한 것도 허용이 된다. 해설 : 주어진 수열의 부분수열을 뒤집는 행위를 세 번 반복하여 1, 2, ... ,N이 되는 수열로 만드는 문제다. 조건 2를 보면 굳이 세 번 뒤집을 필요가 없음을 알 수 있다. 즉, 두 번 뒤집고 1,1을 뒤집거다 한 번 뒤집고 1,1을 두번 뒤집으면 되는 것이다. 우선 처음 수열이 1씩 증가하는 수열이기때문에 이 수열을 세 번 뒤집으면 1씩 증가하거나 1씩 감소하는 부분이 k개 생긴다. ..
