Q2163. 초콜릿 자르기

간단한 수식도 존재하지만 DP로 풀었습니다.

자르는 횟수를 저장하며 나아가는 로직 입니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2163 { static int[][] array; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.valueOf(st.nextToken()); int m = Integer.valueOf(st.nextToken()); array = new int[n+1][m+1]; for (int j = 2; j <= m; j++) { int k = j/2; if (j % 2 == 0) { array[1][j] = array[1][k] + array[1][k] + 1; } else { array[1][j] = array[1][k] + array[1][k+1] + 1; } } for (int i = 2; i <= n; i++) { for (int j = 1; j <= m; j++) { int k = i/2; if (i % 2 == 0) { array[i][j] = array[k][j] + array[k][j] +1; } else { array[i][j] = array[k][j] + array[k+1][j] +1; } } } System.out.println(array[n][m]); } }