ARC_084_A / ABC_077_C - Snuke Festival
n개의 배열 a, b, c가 주어진다. a[i] < b[j] < c[k] 를 만족시키는 모든 쌍의 개수를 구하는 문제. 순서 상관 없으니 정렬부터 해보면 뭔가 보인다. b를 기준으로 살펴보자. b의 원소 중 하나를 정했다면 가 해당 b 원소를 뽑았을 때 만들 수 있는 경우의 수가 된다. 모든 n에 대해 돌리면서 b의 원소를 기준으로 a, c 배열에 대해 이…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 34
52 51 DIVERTA2019_D - DivRem Number
주어진 N에 대해 나눈 몫과 나머지가 같도록 하는 m을 모두 구해 더하면 된다. 수식을 조금 이용하면 된다. 먼저 구하고자 하는 favorite number를 m으로 두면 이 성립해야 되고, 양쪽으로 식을 정리하면 이 된다. 단, 1부터 모든 n까지 탐색은 시간 초과가 되므로 sqrt(n) 까지만 돌려주면 된다.
50 ABC_182_E - Akari
n개의 전구가 4방향으로 빛을 쏘고, m개의 블럭은 빛을 차단한다. 전체 그리드 (H*W)에서 총 몇 칸이 빛이 도달하는지 확인. 간단한 시뮬레이션 문제. 모든 전구에서 상 하 좌 우로 빛을 쏴주면서 카운트를 해주면 된다.
49 ARC_110_C - Exoswap
배열이 주어지고, 임의의 순열 P의 순서대로 swap을 했을 때 오름차순이 되는지 확인하는 문제. 그리디하게 접근해보자. 가장 큰 수는 가장 오른쪽으로 이동해야 되므로 가장 큰 수부터 탐색을 진행한다. 오른쪽으로 swap이 가능하면 swap을 해주고 자기 위치까지 계속 swap을 한다. 일종의 버블 정렬 느낌. 이때 P가 순열이므로 visited를 넣어 한…