생각날때마다 올리는 블로그

Link문제 링크Problem길이가 N인 수열 A1A_1A1​, A2A_2A2​, ..., ANA_NAN​이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.i ji~ji j : Ai, Ai+1, ..., AjA_i,~A_{i+1},~...,~A_jAi​, Ai+1​, ..., Aj​에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N)수열의 인덱스는 1부터 시작한다.연속합은 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이며, 수는 한 개 이상 선택해야 한다.Solution Part I대충 구간에 대한 쿼리를 다루니, 세그먼트 트리가 제일 유력하다.물론, 플래티넘 2의 특성 상 Mo’s algorithm이 판을 치는 단계라지만.. 이건 뭐 구간을 나누어서 따..

Link 문제 링크 Problem 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열과 개수를 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이고, 1개이다. A = {10, 20, 30, 10, 20, 30}인 경우에는 가장 긴 증가하는 부분 수열의 길이는 3이고, 4개가 있다. Input 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) Solution Part I 일단 LIS 문제이고, L..

Link http://icpc.me/2873 Problem 상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다. 어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다. 이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다. 각..