728x90
풀이
정수 K가 적혀있는 N개의 징검다리에 대해 징검다리를 건너며 얻을 수 있는 최대값을 구하는 문제다.
문제에서 주어진 조건 중 아래와 같은 조건이 있다.
N개의 모든 징검다리에 순서대로 1 ~ N의 번호를 붙인다. U번 징검다리에서 V번 징검다리로 점프하기 위해서는, U와 V의 차이가 미리 정해진 값 D 이하여야 한다.
어떤 징검다리도 두 번 이상(한 번을 넘게) 밟을 수는 없다.
때문에, 징검다리의 양 끝이 아닌 중간에서 시작하더라도 왼쪽 또는 오른쪽 방향으로만 진행할 수 있다.
서로 다른 방향이더라도 결국 반대 방향의 부분집합에 속하는 영역이기 때문에 징검다리를 한 방향으로 진행한다고 가정하고 dp로 풀이할 수 있다.
진행 방향은 1번부터 N번이며 D씩 이동한다면 모든 징검다리가 탐색 대상이다.
때문에 불필요한 탐색을 줄이기 위해 이전에 탐색한 영역에 대한 최대값을 update하고 dp값을 갱신하며 풀이했다.
만약, max(1, i - D) ~ (i - 1) 번 징검다리의 최대값이 0이하라면, i번 징검다리의 최대값은 자기 자신이므로 0초과인 경우에만 값을 누적해주자.
소스코드
출처
15678번: 연세워터파크
첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109
www.acmicpc.net
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 1193] 분수찾기 [Java] (0) | 2023.10.04 |
|---|---|
| [백준 1015] 수열 정렬 [Python] (1) | 2023.10.03 |
| [백준 28490] Area [Python] (0) | 2023.09.10 |
| [백준 26495] Big Number [Python] (0) | 2023.09.07 |
| [백준 28282] 운명 [Python] (1) | 2023.09.05 |