π λ¬Έμ
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
μ κ·Έλ¦Όμ ν¬κΈ°κ° 5μΈ μ μ μΌκ°νμ ν λͺ¨μ΅μ΄λ€.
맨 μμΈ΅ 7λΆν° μμν΄μ μλμ μλ μ μ€ νλλ₯Ό μ ννμ¬ μλμΈ΅μΌλ‘ λ΄λ €μ¬ λ, μ΄μ κΉμ§ μ νλ μμ ν©μ΄ μ΅λκ° λλ κ²½λ‘λ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νλΌ. μλμΈ΅μ μλ μλ νμ¬ μΈ΅μμ μ νλ μμ λκ°μ μΌμͺ½ λλ λκ°μ μ€λ₯Έμͺ½μ μλ κ² μ€μμλ§ μ νν μ μλ€.
μΌκ°νμ ν¬κΈ°λ 1 μ΄μ 500 μ΄νμ΄λ€. μΌκ°νμ μ΄λ£¨κ³ μλ κ° μλ λͺ¨λ μ μμ΄λ©°, λ²μλ 0 μ΄μ 9999 μ΄νμ΄λ€.
π μ λ ₯
첫째 μ€μ μΌκ°νμ ν¬κΈ° n(1 β€ n β€ 500)μ΄ μ£Όμ΄μ§κ³ , λμ§Έ μ€λΆν° n+1λ²μ§Έ μ€κΉμ§ μ μ μΌκ°νμ΄ μ£Όμ΄μ§λ€.
π μΆλ ₯
첫째 μ€μ ν©μ΄ μ΅λκ° λλ κ²½λ‘μ μλ μμ ν©μ μΆλ ₯νλ€.
π μμ
μμ μ λ ₯ 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
μμ μΆλ ₯ 1
30
μ½λ κ³Όμ
μ κ·Ό λ°©λ²
- μΌκ°νμ μλ λκ°μ μΌλ‘ λν΄ μ΅μ’ κ°μ₯ ν° κ°μ κ²°μ νλ€.
- μ λ ₯ κ°μμ col(x)μ 1μ΄ μΆκ°κ° λκ³ , row(y)λ μΌμͺ½ λκ°μ κ³Ό μ€λ₯Έμͺ½ λκ°μ μ΄ κ°κ° (y)μ (y+1) μ΄ λλ€. μ¦, μ μ₯λμ΄ μλ κ°μ΄ μκΈ° μμ μ μμΉμμ λ°λ‘ μλμ μμΉνκ±°λ κ·Έ μλμμ μμΌλ‘ 1μ μ΄λν κ²κ³Ό κ°μ κ²μ΄λ€.
- top-down λ°©μμ μ΄μ©νμ¬ μ΅μ’ 맨 μλ νμ ν©μ μ μ₯νμ¬ κ°μ₯ ν° κ°μ λ΅μΌλ‘ μ μ νλ€.
νλ¦° μ½λ
for λ¬Έμ μ¬μ©νμ§ μκ³ , recursionμ μ¬μ©νλ€. for λ¬Έμ μ¬μ©νλ€λ©΄ μ΅λ μκ°λ³΅μ‘λκ° O(n^2) μ΄κΈ° λλ¬Έμ μκ° μ΄κ³Όκ° λ°μνμ§ μλλ€. νμ§λ§, recursionμ top-down λ°©μμΌλ‘ μ§ννκ² λλ€λ©΄ μ΅λ μκ° λ³΅μ‘λλ O(n!)λ‘ ν° κ°μ΄ λμΆλλ€. nμ μ΅λ κ°μ 500μ΄κΈ° λλ¬Έμ μ΅λ μκ° λ³΅μ‘λλ 500!κ° λλ κ²μ΄λ€. λ°λΌμ μλ μ½λλ‘ λ¬Έμ μ κ·Όμ μκ°μ΄κ³ΌλΌλ κ²°κ³Όλ₯Ό μ΄λνλ€.
import java.io.*;
import java.util.*;
public class Main{
public static int[][] arr;
public static int n;
public static int max = 0;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for(int i = 0; i < n ; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int index = 0;
while(st.hasMoreTokens()){
arr[i][index++] = Integer.parseInt(st.nextToken());
}
}
// λ§μ
ν
recurPlus(0, 0, 0);
System.out.println(max);
}
public static void recurPlus(int col, int row, int num){
// 맨 μλμ μμΉν κ²½μ°
if(col == n){
max = Math.max(max, num);
return;
}
recurPlus(col + 1, row, arr[col][row] + num); // left
recurPlus(col + 1, row + 1, arr[col][row] + num); // right
}
}
λ§μ μ½λ
λ°λΌμ, μ΄λ―Έ μ μ₯λμ΄ μλ κ²½μ°μλ λ°λ‘ κ³μ°μ νμ§ μλ DP(Dynamic Programming)μ μ΄μ©νλ€. λ°©λ²μ top-down μμ bottom-up λ°©μμΌλ‘ λ³κ²½νμΌλ©°, νμ¬ μμΉμμ κ³μ°μ΄ μλμ΄ μλ€λ©΄ μλ λ λκ°μ μ κ²°κ³Ό κ°μμ νμ¬ μμ μ κ°μ λν κ²μ΄ λ ν° κ²μ μ μ₯νλ€.
import java.io.*;
import java.util.*;
public class Main{
public static int[][] arr;
public static int[][] dp;
public static int n;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
dp = new int[n][n];
for(int i = 0; i < n ; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int index = 0;
while(st.hasMoreTokens()){
arr[i][index++] = Integer.parseInt(st.nextToken());
}
}
// bottom up λ°©μμ μ¬μ©νκΈ° λλ¬Έμ λ§μ§λ§ μ€μ μλ μλ₯Ό 볡μ¬
for (int i = 0; i < n ; i++){
dp[n-1][i] = arr[n-1][i];
}
System.out.println(recurPlus(0, 0));
}
public static int recurPlus(int col, int row){
// 맨 μλμ μμΉν κ²½μ° μμ μ κ°λ§μ return
if(col == n - 1){
return dp[col][row];
}
if(dp[col][row] == 0){
dp[col][row] = Math.max(recurPlus(col + 1, row), recurPlus(col+1, row+1)) + arr[col][row];
}
return dp[col][row];
}
}
'PS > BaekJoon' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
2108 JAVA ν΅κ³ν (1) | 2024.02.08 |
---|---|
10773 JAVA μ λ‘ (0) | 2024.02.08 |
14888 JAVA μ°μ°μ λΌμλ£κΈ° (1) | 2024.02.04 |
2751 JAVA μ μ λ ¬νκΈ° 2 (0) | 2024.02.04 |
2581 JAVA μμ (0) | 2024.02.04 |
π λ¬Έμ
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
μ κ·Έλ¦Όμ ν¬κΈ°κ° 5μΈ μ μ μΌκ°νμ ν λͺ¨μ΅μ΄λ€.
맨 μμΈ΅ 7λΆν° μμν΄μ μλμ μλ μ μ€ νλλ₯Ό μ ννμ¬ μλμΈ΅μΌλ‘ λ΄λ €μ¬ λ, μ΄μ κΉμ§ μ νλ μμ ν©μ΄ μ΅λκ° λλ κ²½λ‘λ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νλΌ. μλμΈ΅μ μλ μλ νμ¬ μΈ΅μμ μ νλ μμ λκ°μ μΌμͺ½ λλ λκ°μ μ€λ₯Έμͺ½μ μλ κ² μ€μμλ§ μ νν μ μλ€.
μΌκ°νμ ν¬κΈ°λ 1 μ΄μ 500 μ΄νμ΄λ€. μΌκ°νμ μ΄λ£¨κ³ μλ κ° μλ λͺ¨λ μ μμ΄λ©°, λ²μλ 0 μ΄μ 9999 μ΄νμ΄λ€.
π μ λ ₯
첫째 μ€μ μΌκ°νμ ν¬κΈ° n(1 β€ n β€ 500)μ΄ μ£Όμ΄μ§κ³ , λμ§Έ μ€λΆν° n+1λ²μ§Έ μ€κΉμ§ μ μ μΌκ°νμ΄ μ£Όμ΄μ§λ€.
π μΆλ ₯
첫째 μ€μ ν©μ΄ μ΅λκ° λλ κ²½λ‘μ μλ μμ ν©μ μΆλ ₯νλ€.
π μμ
μμ μ λ ₯ 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
μμ μΆλ ₯ 1
30
μ½λ κ³Όμ
μ κ·Ό λ°©λ²
- μΌκ°νμ μλ λκ°μ μΌλ‘ λν΄ μ΅μ’ κ°μ₯ ν° κ°μ κ²°μ νλ€.
- μ λ ₯ κ°μμ col(x)μ 1μ΄ μΆκ°κ° λκ³ , row(y)λ μΌμͺ½ λκ°μ κ³Ό μ€λ₯Έμͺ½ λκ°μ μ΄ κ°κ° (y)μ (y+1) μ΄ λλ€. μ¦, μ μ₯λμ΄ μλ κ°μ΄ μκΈ° μμ μ μμΉμμ λ°λ‘ μλμ μμΉνκ±°λ κ·Έ μλμμ μμΌλ‘ 1μ μ΄λν κ²κ³Ό κ°μ κ²μ΄λ€.
- top-down λ°©μμ μ΄μ©νμ¬ μ΅μ’ 맨 μλ νμ ν©μ μ μ₯νμ¬ κ°μ₯ ν° κ°μ λ΅μΌλ‘ μ μ νλ€.
νλ¦° μ½λ
for λ¬Έμ μ¬μ©νμ§ μκ³ , recursionμ μ¬μ©νλ€. for λ¬Έμ μ¬μ©νλ€λ©΄ μ΅λ μκ°λ³΅μ‘λκ° O(n^2) μ΄κΈ° λλ¬Έμ μκ° μ΄κ³Όκ° λ°μνμ§ μλλ€. νμ§λ§, recursionμ top-down λ°©μμΌλ‘ μ§ννκ² λλ€λ©΄ μ΅λ μκ° λ³΅μ‘λλ O(n!)λ‘ ν° κ°μ΄ λμΆλλ€. nμ μ΅λ κ°μ 500μ΄κΈ° λλ¬Έμ μ΅λ μκ° λ³΅μ‘λλ 500!κ° λλ κ²μ΄λ€. λ°λΌμ μλ μ½λλ‘ λ¬Έμ μ κ·Όμ μκ°μ΄κ³ΌλΌλ κ²°κ³Όλ₯Ό μ΄λνλ€.
import java.io.*;
import java.util.*;
public class Main{
public static int[][] arr;
public static int n;
public static int max = 0;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for(int i = 0; i < n ; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int index = 0;
while(st.hasMoreTokens()){
arr[i][index++] = Integer.parseInt(st.nextToken());
}
}
// λ§μ
ν
recurPlus(0, 0, 0);
System.out.println(max);
}
public static void recurPlus(int col, int row, int num){
// 맨 μλμ μμΉν κ²½μ°
if(col == n){
max = Math.max(max, num);
return;
}
recurPlus(col + 1, row, arr[col][row] + num); // left
recurPlus(col + 1, row + 1, arr[col][row] + num); // right
}
}
λ§μ μ½λ
λ°λΌμ, μ΄λ―Έ μ μ₯λμ΄ μλ κ²½μ°μλ λ°λ‘ κ³μ°μ νμ§ μλ DP(Dynamic Programming)μ μ΄μ©νλ€. λ°©λ²μ top-down μμ bottom-up λ°©μμΌλ‘ λ³κ²½νμΌλ©°, νμ¬ μμΉμμ κ³μ°μ΄ μλμ΄ μλ€λ©΄ μλ λ λκ°μ μ κ²°κ³Ό κ°μμ νμ¬ μμ μ κ°μ λν κ²μ΄ λ ν° κ²μ μ μ₯νλ€.
import java.io.*;
import java.util.*;
public class Main{
public static int[][] arr;
public static int[][] dp;
public static int n;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
dp = new int[n][n];
for(int i = 0; i < n ; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int index = 0;
while(st.hasMoreTokens()){
arr[i][index++] = Integer.parseInt(st.nextToken());
}
}
// bottom up λ°©μμ μ¬μ©νκΈ° λλ¬Έμ λ§μ§λ§ μ€μ μλ μλ₯Ό 볡μ¬
for (int i = 0; i < n ; i++){
dp[n-1][i] = arr[n-1][i];
}
System.out.println(recurPlus(0, 0));
}
public static int recurPlus(int col, int row){
// 맨 μλμ μμΉν κ²½μ° μμ μ κ°λ§μ return
if(col == n - 1){
return dp[col][row];
}
if(dp[col][row] == 0){
dp[col][row] = Math.max(recurPlus(col + 1, row), recurPlus(col+1, row+1)) + arr[col][row];
}
return dp[col][row];
}
}
'PS > BaekJoon' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
2108 JAVA ν΅κ³ν (1) | 2024.02.08 |
---|---|
10773 JAVA μ λ‘ (0) | 2024.02.08 |
14888 JAVA μ°μ°μ λΌμλ£κΈ° (1) | 2024.02.04 |
2751 JAVA μ μ λ ¬νκΈ° 2 (0) | 2024.02.04 |
2581 JAVA μμ (0) | 2024.02.04 |