17611번: 직각다각형 입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (xi, yi)가 차례대로 주어진다. 주어지 www.acmicpc.net 1. 문제 요약 다각형의 좌표가 주어지고 수직선과, 수평선에 대하여 해당 다각형의 수직선분과, 수평선분이 가장 많이 교차하는 횟수를 구하라. 2. 접근 방법 백준 - 3020 개똥벌레 [누적합][이모스] 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종 e-room.tistory.com 해당 문제..
3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 1. 문제 요약 장애물의 위치가 주어지고, 해당 장애물을 통과하는 최솟값과 그러한 구간의 수를 출력하라 2. 접근 방법 위와 같은 장애물이 있다고 했을 때, 아래서부터 장애물을 통과하는 수를 세어보면 3, 3, 2, 3 입니다. 이런 식으로 완전탐색으로도 충분히 정답은 구할 수 있습니다만, 시간과 메모리가 한정되어 있기 때문에 다른 방법으로 풀어야 합니다. 이모스법 알고리즘을 알고 있다면 쉽게 풀 수 있습니다. 위 그림과 같이 장애물이 시작되는 위치에 +1, 끝나는..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 N x N의 표가 주어지고 좌표가 주어지면, 그 구간의 합계를 구하는 문제이다. 2. 접근 방법 다이내믹 프로그래밍을 이용하여 각각의 구간별 합을 미리 구해놓는다. (DP 테이블) 예를 들어, DP 테이블의 (2,2)의 위치는 기존테이블의 (2,2) + DP(2,1) + DP(1,2) - DP(1,1)이다 즉, 원하는 위치의 수 + DP테이블의 위 + 좌 - 겹치는 구간이다 DP테이블은 (N+1) x (N+1)로 생성하면 편리하다..
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 간단 요약 해당 문제는 수열이 주어지면, 해당 수열의 부분연속수열의 합중 가장 큰 값을 구하는 문제이다. 2. 접근 방법 순차적으로 값을 더한다. 다음에 올 숫자가 이득인지 손해인지를 판단한다. 현재까지의 값 + 수열의 현재 인덱스의 값 vs 수열의 현재 인덱스의 값을 비교하여 더 큰 값을 취한다. 예를 들어 아래와 같은 수가 주어질 경우 -4는 음수이지만 10과 합하면 6이다. 해당 값과 3을 더하면 9이므로, 3보다 크기때문에 손해가 아니므로 취한다. 아래처럼 2..
