<Algorithm> 69. 2163번 초콜릿 자르기

1. 2163번 초콜릿 자르기

• 간단한 DP문제, 1열은 1x1 초콜릿이 늘어나기 때문에 1개씩 늘려주고 그외 2열부터는 1열의 초콜릿을 이어붙이는 것과 같다.

• 2열은 추가 될때마다 잘라야 될 라인이 하나씩 증가하고 거기에 행에 대응하는 초콜릿의 자르는 부분을 추가하면 된다. 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt()+1;
        int M = sc.nextInt()+1;
        
        int[][] dp = new int[1001][1001];
        
        for(int i = 1; i < N; i++ ) {
            for(int j = 1; j < M; j++) {
                if(j == 1) {
                    dp[i][j] = i - 1;
                }else {
                    dp[i][j] = dp[i][j-1] + i;                    
                }
            }
        }
        System.out.println(dp[N - 1][M - 1]);
    }
}
 

참고 & 출처