Q2240. 자두나무

최대 열매 획득 개수를 저장하며 나아가는 로직입니다.

개인적으로 어려웠습니다.

코드에 주석을 달아놨으니, 참고하세요.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2240 { static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br =  new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.parseInt(st.nextToken()); int moveNum = Integer.parseInt(st.nextToken()); dp = new int[num+1][moveNum+1]; for (int i = 1; i <= num; i++) { st = new StringTokenizer(br.readLine()); int treeNum = Integer.parseInt(st.nextToken()); for (int j = 0; j <= moveNum; j++) { if (treeNum == 1) { if (j%2 == 0) { //현재 위치한 나무에서 자두가 떨어질 경우(이동 횟수가 짝수인 경우) if (j == 0) { //이동을 한번도 하지 않았을 경우 dp[i][0] = dp[i-1][0] + 1; } else { //이동을 한번이라도 한 경우 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + 1; } } else { //현재 위치한 나무에서 자두가 떨어지지 않을 경우 if (j == 0) { //이동을 한번도 하지 않았을 경우 dp[i][0] = dp[i-1][0]; } else { //이동을 한번이라도 한 경우 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]); } } } else { if (j%2 == 1) { //현재 위치한 나무에서 자두가 떨어질 경우(이동 횟수가 홀수인 경우) if (j == 0) { dp[i][0] = dp[i-1][0] + 1; } else { dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + 1; } } else { //현재 위치한 나무에서 자두가 떨어지지 않을 경우 if (j == 0) { dp[i][0] = dp[i-1][0]; } else { dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]); } } } } } int maxResult = dp[num][0]; for (int j = 1; j <= moveNum; j++) { maxResult = Math.max(maxResult, dp[num][j]); } System.out.println(maxResult); } }