복습노트 복습노트

문제 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 왼쪽부터 차례대로 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 www.acmicpc.net N개에 돌에 부여된 수 A1, A2, A3, ... An 이 있다. 여기서 맨 왼쪽 돌부터 오른쪽 방향으로만 이동하여 An에 도달할 수 있는지 구하는 문제이다. 문제의 조건은 다음과 같다. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다. i번째 돌에서 j(i < j)번째 돌로 이동할 때 (j - i) × (1 + |Ai - Aj|) 만큼 힘을 쓴다. 내가 처음에 접근한 방법은 다음과 같다. d..

문제 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 사탕상자에서 조건에 따라 사탕을 꺼내고 사탕의 맛을 출력하는 문제이다. 사탕의 맛은 1 ~ 100000 이고, 1이 제일 맛있는 맛이다. 입력은 처음에 n이 주어진다. n은 쿼리를 수행할 횟수이다. 이제 n번의 쿼리가 나온다. a = 1 일경우 a b가 입력으로 들어오고 순위가 b인 사탕으로 꺼내고 해당 사탕의 맛을 출력하는 것이다. a = 2 일 경우 a b c가 입력으로 들어오고 맛이 b인 사탕 c개를 추가해준다. 예를 들어 ..

문제 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net n개의 밑변의 길이가 1이고 높이가 다른 직사각형이 주어지면, 가장 큰 직사각형을 구하는 문제이다. 이전에 스택으로 푼 문제지만, 이번에는 세그먼트 트리를 이용해 문제를 풀어보겠다. 중요한 것은 0 ~ n-1 의 구간이 있으면, 구간을 돌아보면서 만들 수 있는 가장 큰 직사각형을 return 한다. 따라서 구간의 가장 큰 직사각형의 넓이는 구간 중 가장 작은 높이와 구간의 길이를 곱해주면 된다. 이를..

문제 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net N개의 행렬이 주어지면 주어진 순서대로 행렬 곱을 할때 가장 적은 연산횟수를 구하는 문제이다. 예를 들어 A = (5, 3), B = (3, 2), C = (2, 6) 으로 주어졌다고 하면 AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다. BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 12..

문제 2423번: 전구를 켜라 첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다. www.acmicpc.net N * M의 직사각형이 주어진다. 또한 전선의 정보도 위와 같이 주어진다. 여기서 전선은 90도 회전할 수 있다. 이때 맨 왼쪽 상단에서 부터 시작해서 맨 오른쪽 하단에 도달할 때 전선의 회전횟수가 최소로 가게끔 하여 맨 아래 우측에 도달하는 전선의 최소 회전횟수를 구하는 문제이다. 위 예시에서 보면 4번째 열에 해당하는 모든 전선들은 90도 회전하면 전구에 도달할 수 있다. 입력 3 5 \\/\\ \\/// /\\\\ 정답 1 여기서 입력이 위와 같이 / 나 \ 로 주어지기..

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 규칙을 찾아보자. N = 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9 즉, 9개이다. N = 2이면 10, 12, 21, 23, 32, 34, ...78, 87, 89, 98 즉, 17개 이다. N = 3이면 101, 121, 123, 210, 212, .....878, 879, 898, 987, 989 즉, 32개이다. 규칙이 보이지 않는다. 처음에는 점..

문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net N * N의 2차원 배열이 있으면 arr[0][0] 부터 시작해서 현재 위치한 값에 해당하는 만큼 오른쪽 과 아래로 점프할 수 있다. 이 때 arr[N-1][N-1]로 도달 할 수 있는 경우의 수를 구하는 문제이다. 예를 들어 그림 1과 같은 상황이 주어진다면 정답은 3이다. 먼저 dp식을 세울 수 있었다. dp[i][j] = x arr[i][j]에 도달할 수 있는 경우의 수는 x 개이다. 점화식을 세우는것은 어렵지 않았지만, 현재 위치에서 칸에..

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net N개의 수열이 주어지면, 연속합이 가장 큰 최댓값을 구하는 문제이다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. dp를 사용할 것이다. dp[i] = i번째 인덱스까지 탐색한 최댓값이다. 따라서 처음 base case는 dp[0] = arr[0]이다. public class Main { public static void main(String[] args)..