PS

https://www.acmicpc.net/problem/23820 mex(S)는 S에 포함되지 않은 가장 작은 음이 아닌 정수이다.이 때 mex({ai * aj})를 구하는 문제이다. ai의 범위는 200만 이하의 음이 아닌 정수이고, 곱으로 집합의 원소를 결정하므로 절대로 나올 수 없는 가장 작은 소수는 계산해보니 2000003이다.그러므로 어떤 수를 곱하던지 상관 없이 2000003을 넘어간다면 즉시 종료하면 되고,모든 가능한 곱을 다 계산한 이후 0 ~ 2000003까지 나오지 않은 정수를 파악하면 된다.    12345678910111213141516171819202122232425262728293031#include iostream>#include vector>#include algorithm..

https://www.acmicpc.net/problem/10986 풀면서 그렇게 어려운 문제는 아니었으나, 오랜만에 보니 잘 기억이 안나서 정리 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하라는 문제인데,보자마자 배열에 나머지만을 저장해도 되겠다는 생각이 들었다.또한, 연속된 구간의 개수이므로 누적합을 이용해야지 시간초과를 방지하지 않을까라는 생각도 들었다.12345678910111213141516171819#include iostream>using namespace std;int sum[1000001], cnt[1001];int main(){    ios_base::sync_with_stdio(false);    cin.tie(0); cout.tie(0);  ..

https://www.acmicpc.net/problem/1736 1736번: 쓰레기 치우기 방은 세로 N, 가로 M (1 ≤ N, M ≤ 100) 크기의 격자 판으로 표현할 수 있다. 왼쪽 위의 위치를 (0, 0)이라 하고, 오른쪽 아래를 (N - 1, M - 1)이라고 하자. 이 판의 몇몇 칸에는 쓰레기가 놓여 있다. 쓰레 www.acmicpc.net 4637번: Robots 위의 문제와 상당히 유사한 문제이다. 접근했던 방법은 로봇이 오른쪽과 아래만 움직일 수 있으므로 x나 y 방향으로 감소할 수 없다는 점을 이용했다. 만약 현재 로봇이 (4, 6)에 위치한다면 당연히 (4, 7) 또는 (5, 6)으로 이동을 할 것이고, 최소의 로봇 개수를 파악해야하므로 먼저 위에서부터 채우는 방식으로 접근했다. ..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 세그먼트 트리 응용 문제 세그먼트 트리를 이용해 구간 합을 미리 구하거나 최솟값을 적는 등으로 활용이 가능했으나, 해당 문제에서는 tree[node]에 가장 작은 값의 인덱스를 집어 넣어 문제를 해결할 수 있다. 원리는 아래와 같다. 예제로 살펴보면, 먼저 가장 작은 값의 인덱스인 1을 기준으로 히스토그램의 넓이를 구한다. 이후 1의 왼쪽과 오른쪽을 다시 기준으로 ..

https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 처음에 0이 존재 다음에는 이를 비트반전 시킨 문자열을 뒤에 추가한다. 이를 무한으로 반복했을 때 N번째 자리의 숫자를 구하는 문제 0 01 0110 01101001 0110100110010110 ... 이렇게 증가하는데, 여기에는 규칙이 있다. 만약 N번째 자리의 수를 구한다면, N번째 자리의 숫자는 N - 2^x의 숫자를 반전 시킨 값이다. N - 2^x는 1이 되거..