-
[알고리즘-JAVA] 백준 알고리즘 2579번 - 계단 오르기알고리즘 2019. 8. 16. 03:23
처음 실패했던 코드.
import java.util.Scanner; import java.lang.Math; public class Main { public static int d[]; public static int arr[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = sc.nextInt(); d = new int[count]; arr = new int[count]; for (int i = 0; i < count; i++) { arr[i] = sc.nextInt(); } if (count == 1) { System.out.println(arr[0]); } else if (count == 2) { System.out.println(arr[0] + arr[1]); } else { d[0] = arr[0]; d[1] = arr[0] + arr[1]; d[2] = Math.max(arr[0] + arr[1], arr[1] + arr[2]); for (int i = 3; i < count - 1; i++) { d[i] = Math.max(d[i - 3] + arr[i - 1] + arr[i], Math.max(d[i - 2] + arr[i], d[i - 1])); } if (count >= 4) { d[count - 1] = Math.max(d[count - 1 - 3] + arr[count - 2] + arr[count - 1], d[count - 1 - 2] + arr[count - 1]); } int max = d[0]; for (int i = 1; i < count; i++) { if (d[i] > max) { max = d[i]; } } System.out.println(max); } } }
성공한 코드
import java.util.Scanner; import java.lang.Math; public class Main { public static int d[][]; public static int arr[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = sc.nextInt(); d = new int[count + 1][3]; arr = new int[count + 1]; for (int i = 1; i <= count; i++) { arr[i] = sc.nextInt(); } d[1][1] = arr[1]; if (count >= 2) { for (int i = 2; i <= count; i++) { d[i][2] = d[i - 1][1] + arr[i]; d[i][1] = Math.max(d[i - 2][1], d[i - 2][2]) + arr[i]; } } System.out.println(Math.max(d[count][2],d[count][1])); } }
이중배열에 더 익숙해져야겠다.
'알고리즘' 카테고리의 다른 글
[알고리즘-JAVA]백준 알고리즘 1699번 - 제곱수의 합 (0) 2019.08.22 [알고리즘-JAVA] 백준 알고리즘 1912번 - 연속합 (0) 2019.08.15 [알고리즘-JAVA] 백준 알고리즘 11053번 - 가장 긴 증가하는 부분수열 (0) 2019.08.15 [알고리즘-JAVA] 백준 알고리즘 2156번 - 포도주 시식 (0) 2019.08.15 [알고리즘-JAVA] 머지소트(Merge Sort)구현 (0) 2019.08.11