문제

데스노트

풀이

폭과 너비를 주고 문자를 한줄에 작성을 다 하지 못하면 다음 줄에 작성할 수 있도록 하는데, 한줄에 남은 오른쪽의 반칸 숫자를 제곱하여 더하여 제출하는 문제이다.

top-down 으로 풀려고 했는데 실력부족으로 도저히 안되서
검색해보니 다들 dfs 로 풀어서 일단 결국 DFS로 되었다. 1000줄 밖에 안되서 DFS로 되는거 일텐데

	private static int dfs(int index) {
    	// 남은 칸수가 존재 하는 값
        if (dp[index] < Integer.MAX_VALUE) {
            return dp[index];
        }
        int k = m - arr[index]; // 남은 칸수
        for (int i = index + 1; i <= n && k >= 0; i++) {
            if (i == n) { // 한줄이 다 체워져 있는 경우
                dp[index] = 0;
                break;
            }
            // 이어 붙인 경우와 이어 붙이지 않은 경우의 수중 가장 작은 값을 갱신한다
            dp[index] = Math.min(dp[index], (k * k) + dfs(i));
            // 남은 칸수를 갱신한다
            k -= arr[i] + 1;
        }
        return dp[index];
    }

어렵다 다시 봐도, dfs의 성질을 보면 가장 마지막 arr이 먼저 dp배열에 갱신되는데 for문 안에 백트래킹 되어 이전에 갱신된 부분을 접근할때 가장 까다로운것 같다 (허접이다)

전체 코드

전체 코드