👀 문제
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXE0gpIa3dADFAVX
👊 도전
1. 설계
- DP를 이용한다.
- 시간 제한 때문에 DP를 배열이 아닌 변수를 이용해 문제를 풀어야 한다.
- Scanner 대신 BufferedReader를 사용해 실행 시간을 줄인다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.io.FileInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
*
* @author HEESOO
*
*/
class Solution
{
public static void main(String args[]) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int T;
T=Integer.parseInt(st.nextToken());
for(int test_case = 1; test_case <= T; test_case++)
{
st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
st=new StringTokenizer(br.readLine());
long answer=0, one=0, two=0;
answer=Long.parseLong(st.nextToken());
if(n>=2) {
one=answer;
two=Math.max(one, Long.parseLong(st.nextToken()));
answer=two;//n==2인 경우를 위함
for(int i=3;i<=n;i++) {
long num=Long.parseLong(st.nextToken());
answer=Math.max(one+num, two);
one=two;
two=answer;
}
}
System.out.println("#"+test_case+" "+answer);
}
return;
}
}
3. 결과
🤟 성공 🤟
초기에는 DP를 배열로 풀어서 시간 초과가 발생하였다. 이후 런타임 에러는 마지막에 main 마지막에 return을 추가하고, long으로 입력받아야 하는 곳을 수정하고, main에 throws IOException을 추가해서 해결했다.
4. 설명
- DP를 이용한다
- dp[i]=Math.max(dp[i-2]+a[i], dp[i-1]), i번째를 침공할 때 개구리의 최대값이다.
- dp[1]=a[1]: 침공할 곳이 하나밖에 없으므로
- dp[2]=Math.max(a[1], a[2]): 1과 2 중 더 큰 값을 쓴다
- dp[3]=Math.max(a[1]+a[3], a[2]): 1을 침공하면 3, 3은 1을 쓸 수 있고, 아니면 2 하나만 선택할 수도 있다
- dp[4]=Math.max(a[1]+a[3], a[2]+a[4], a[1]+a[4])
== max(dp[3], max(a[2], a[1])+a[4])
== max(dp[3], dp[2]+a[4]) - 그런데 이 문제는 배열을 사용하면 시간 초과가 발생한다. 따라서 dp대신 변수 answer, one, two를 사용한다.
- answer은 i일때 값, one은 i-1, two는 i-2 값을 저장한다.
- 실행 시간을 줄인다
- Scanner보다 BufferedReader 속도가 더 빠르므로 이를 사용한다.
👏 해결 완료!
참고
- [SWEA] 9780 외계인 침공 https://octorbirth.tistory.com/393