https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 주어진 배열의 구간 합이 m으로 나누어떨어지는 경우의 수를 구하는 문제 제출하고 다른 사람들의 풀이를 보니 다들 조합으로 풀어서 신기했던 문제이다. 조합으로 푸는 방법은 생각지도 못했는데, 다른 사람들의 풀이를 보니 조합으로 접근했어도 괜찮았을 듯 싶다. 우선 배열 i ~ j의 누적 합을 구해주는데, 어차피 나머지가 중요하므로 나머지의 누적 합을 구..
BOJ
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이 되거..
https://www.acmicpc.net/problem/26093 26093번: 고양이 목에 리본 달기 첫 번째 줄에는 고양이의 수 $N$과 리본 종류의 수 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 100, 2 \leq K \leq 10\,000)$ 다음 $N$개의 줄에는 각각 $K$개의 정수 $a_{i,1}, \cdots, a_{i,k}$이 공백으로 구 www.acmicpc.net 양 옆에 위치한 고양이와 방울의 종류가 같지 않도록 함과 동시에 만족도를 최고로 높이는 방법을 찾아야한다. 그래서 접근한 방법은 단순히 이전 고양이의 가장 높은 만족도의 방울 번호와 다음으로 높은 만족도의 방울 번호를 저장하여 현재 순서의 고양이의 방울 번호와 비교하여 만족도의 합을 저장하는 방식이..
