본문 바로가기

전체 글

 (128)
11873 - 최대 직사각형 step 1더보기https://www.acmicpc.net/problem/6549https://codestudycafe.tistory.com/37step 2더보기"직사각형의 밑변이 i번째 행에 있다면 만들 수 있는 직사각형의 최대 넓이는 얼마일까" 라는 질문을 모든 행에 대해서 하면 됩니다.i가 정해졌다고 할 때, 0 위에 있는 1들은 아무 의미 없습니다. 그곳에 직사각형이 도달할 수 없기 때문이죠. 아래는 예제의 첫번째 케이스에서 i=3일 때입니다.그렇다면 이 문제는 "히스토그램에서 가장 넓은 직사각형이 무엇인가"를 푸는 문제로 바뀝니다.이 문제를 푸는데 N, 이 문제의 개수가 N이므로 N^2에 해결할 수 있습니다.코드더보기#include#includeusing namespace std;stack> s..
13537 - 수열과 쿼리 1 step 1더보기원래 있는 수열을 쿼리로 변환해 봅시다.그럼 문제는 다음과 같이 바뀝니다. 길이 $N$인 수열이 주어집니다. 처음 수열의 값은 전부 0입니다.$1 i k$ : 수열 $i$번째 위치에 $k$를 추가합니다.$2 i j k$ : $A_i, A_{i+1}, ..., A_j$로 이루어진 부분 수열 중에서 $k$보다 큰 원소의 개수를 출력한다.step 2더보기$2 i j k$를 봅시다. 수열에서 $k$ 이하인 숫자들은 아무 의미가 없습니다. $k$ 초과인 숫자들은 $k$보다 크다는 것이 중요하지 그 숫자의 값은 중요하지 않습니다.그럼 이 쿼리들을 $k$가 큰 순서로, $k$가 같으면 2번 쿼리가 먼저 나오도록 정렬해 봅시다. 세그먼트 트리를 하나 만든 다음 1번 쿼리고 오면 $i$에 1 추가, 2번..
1055 - 끝이없음 step 1더보기max - min은 대략 100만큼 차이 납니다. 그럼 "i번째 문자가 무엇인가"라는 문제를 i가 min, min+1, ..., max일 때까지 해서 총 100번 물어보면 됩니다. 앞으로의 설명에서는 i번째 문자를 구하는 데에 집중하겠습니다.step 2더보기$ 기호가 1개일 때와 2개일 때로 나눌 수 있습니다. $가 1개일 때 먼저 처리하겠습니다. S를 $ 기준으로 앞과 뒤로 나눌 수 있습니다. $ 앞을 (1), $ 뒤를 (2)라고 하면 (1) (1) (1).... (1) (1) (입력) (2) (2) (2)... (2) (2) 로 만들어 집니다. (1)과 (2)는 (실행시킨 횟수)만큼 반복됩니다. (1)과 (2)의 길이를 구해두면 쉽게 풀 수 있습니다.step 3더보기N번 실행시켰을 때..

티스토리툴바