728x90
반응형
문제
https://www.acmicpc.net/problem/2579
풀이 방법
각 계단에는 점수가 있고, 계단을 밟으면 점수를 얻을 수 있다.
대신에 한번에 최대 두 칸까지만 오를 수 있고, 연속한 세개의 계단을 밟을 수 없다.
얻을 수 있는 최대 점수를 구하면 되는 문제다.
dp를 사용해서 풀었다. dp[i]의 값은 i번째 계단은 밟는다는 것을 가정하고, i-1번째, i 번째 연속해서 밟는 경우와 i-2번째, i번째 한 칸 뛰어 넘고 밟는 경우 중에서 더 큰 점수를 가진 경우를 저장했다.
연속해서 밟는 경우는 연속 3개는 밟으면 안되기 때문에 dp[i-3]의 값을 더해줘야한다.
제출 코드
import java.io.*;
public class BJ_2579_계단오르기 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] map = new int[N + 1];
int[] dp = new int[N + 1];
for (int i = 1; i <= N; i++) {
map[i] = Integer.parseInt(br.readLine());
}
dp[1] = map[1];
if (N > 1)
dp[2] = map[1] + map[2];
for (int i = 3; i <= N; i++) {
dp[i] = Math.max(dp[i - 3] + map[i - 1] + map[i], dp[i - 2] + map[i]);
}
System.out.println(dp[N]);
}
}
728x90
반응형
'알고리즘 > BJ' 카테고리의 다른 글
[BJ] 백준 21610 마법사 상어와 비바라기 (JAVA) (0) | 2022.06.22 |
---|---|
[BJ] 백준 20058 마법사 상어와 파이어스톰 (JAVA) (0) | 2022.06.16 |
[BJ] 백준 2748 피보나치 수2 (JAVA) (0) | 2022.04.13 |
[BJ] 백준 1003 피보나치 함수 (JAVA) (0) | 2022.04.12 |
[BJ] 백준 1012 유기농 배추 (JAVA) (0) | 2022.03.30 |