기록

문제 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 풀이 1) 연속 누적합 dp 우선, 보석의 개수를 신경쓰지 않고, 연속해서 얻을 수 있는 보석의 누적 가치합을 구한다. 이를 위해 세가지 경우를 고려한다. 이전 보석과 연속해서 줍는다. 이전 보석을 버리고, 현재 보석만을 줍는다. 아무 보석도 줍지 않는다. 2) M개 이상의 보석을 줍는다. prefix_sum 2-1. 현재 위치를 포함해서, 왼쪽으로 이동하면서 M개의 보석을 줍는다..

문제 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 1) 첫번째 집에 사용할 페인트 색 고르기 첫번째 집과 마지막 집에 사용되는 페인트가 달라야 한다는 조건을 만족하기 위해 경우의 수를 나누어 계산하였다. 1. 첫번째 집에 빨간색 페인트를 사용한다. 두번째 집과 마지막 집의 빨간색 페인트가 선택되지 않기 위해서 충분히 큰 값을 넣는다. 첫번째 집의 초록색과 파란색 페인트가 선택되지 않기 위해서 충분히 큰 값을..

보호되어 있는 글입니다.

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 첫번째 열에 속하는 두 값을 제외하고 연산을 시작한다. 제한사항에 따르면 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 함께 사용할 수 없다. 이 조건을 이용하여 왼쪽에서 오른쪽으로 진행하면서 max(왼쪽 대각선 값+현재 값, 왼쪽값)을 연산하였다. # 초기상태 [50, 10, 100, 20, 40] [30, 50, 70, 10, 60] # n = 1 [50, 50, 100, 20, 40] [30, 100, 70, 10, 60] #..