![]()
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 양 옆에 위치한 고양이와 방울의 종류가 같지 않도록 함과 동시에 만족도를 최고로 높이는 방법을 찾아야한다. 그래서 접근한 방법은 단순히 이전 고양이의 가장 높은 만족도의 방울 번호와 다음으로 높은 만족도의 방울 번호를 저장하여 현재 순서의 고양이의 방울 번호와 비교하여 만족도의 합을 저장하는 방식이..
https://www.acmicpc.net/problem/27651 27651번: 벌레컷 크기 $N$의 $1$차원 양의 정수 배열로 이루어진 자벌레가 있다. 자벌레는 곤충이기 때문에 머리, 가슴, 배로 부위를 구분할 수 있다. 각 부위는 배열상에서 연속하는 구간으로 나타낼 수 있으며 배 www.acmicpc.net 주어진 수열을 3분할하는데, 이를 각각 머리, 가슴, 배라고 지칭한다. 1 ~ x 의 크기 < y + 1 ~ n의 크기 < x + 1 ~ y 를 만족하는 수열의 개수를 구해야한다. 즉, 머리 < 배 < 가슴을 만족해야한다. 이를 위해 우선 1 ~ n까지의 수열의 합을 배열에 저장해주어 중복으로 덧셈을 실시하는 일이 발생하지 않도록 누적합을 이용했다. 먼저 1 ~ x를 구하는 것은 간단하다. 단..
