boj)9465 - 스티커
2020. 9. 19. 14:25ㆍPS/boj
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class boj_9465 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st, st2;
static int[][] dp;
static int[][] val;
static int t;
public static void main(String[] args) throws IOException {
t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
st2 = new StringTokenizer(br.readLine());
val = new int[3][n];
for (int j = 0; j < n; j++) {
val[1][j] = Integer.parseInt(st.nextToken());
val[2][j] = Integer.parseInt(st2.nextToken());
}
dp = new int[3][n];
dp[1][0] = val[1][0]; dp[2][0] = val[2][0];
for (int j = 1; j < n; j++) {
dp[0][j] = Math.max(Math.max(dp[0][j-1], dp[1][j-1]), dp[2][j-1]);
dp[1][j] = Math.max(dp[0][j-1], dp[2][j-1]) + val[1][j];
dp[2][j] = Math.max(dp[0][j-1], dp[1][j-1]) + val[2][j];
}
System.out.println(Math.max(Math.max(dp[0][n-1], dp[1][n-1]), dp[2][n-1]));
}
}
}
- 스티커의 마지막 부분에 초점
- 경우의수 아무것도 때지않는 경우 0, 위에칸 1, 아래칸 2
- dp[x][n] :: 길이가 n이고 마지막 n 번째일때 때는 스티커가 x 인 점화식 ( x = 0, 1, 2 )
- dp[x][n] = max( dp[x가 아닌 수][n-1] ) + val[x][n] (x 가 0일때는 포함하지않음)
- 0, 1, 2를 n 번째에서 땟을때의 경우의 수 들 중에 최댓값이 ans
'PS > boj' 카테고리의 다른 글
boj)1932 - 정수 삼각형 (0) | 2020.09.19 |
---|---|
boj)2156 - 포도주 시식 (0) | 2020.09.19 |
boj)11057 - 오르막수 (0) | 2020.09.19 |
boj)1309 - 동물원 (0) | 2020.09.19 |
boj)1149 - RGB 거리 (0) | 2020.09.19 |