글 읽기 - 어디에서 생각을 잘못 했는지 모르겠습니다.

grapecw 3년 전 0

완료 코드가 아니라 중간 코드이긴 한데...

예제를 기준으로 출력했을 때

52~55줄의

if (remain >= names[pos] + 1) {
dp[line][pos] = Math.min(dp[line][pos], getBlankCnt(pos + 1, line, remain - (names[pos] + 1)));
}
dp[line][pos] = Math.min(dp[line][pos], getBlankCnt(pos + 1, line + 1, m - names[pos]) + remain * remain);

이 부분을 이렇게 설정하고 돌리면 답이 61이 나옵니다.

하지만,

이것을 고쳐서

dp[line][pos] = Math.min(dp[line][pos], getBlankCnt(pos + 1, line + 1, m - names[pos]) + remain * remain);

if (remain >= names[pos] + 1) {
dp[line][pos] = Math.min(dp[line][pos], getBlankCnt(pos + 1, line, remain - (names[pos] + 1)));
}

로 바꿔서 돌리게 되면 출력이 1이 나오게 됩니다.

순서라곤 해도 아직 dp에 따라 재귀를 반복 안 하게 설정 한 것도 아니니 똑같은 값인 61이 나와야 할거 같은데

어째서 이런 현상이 나오는지 이해가 되지 않습니다.

혹시 이 부분에 대한 지식을 나눠 주실 수 있으시면 감사드리겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/2281
public class Main {
    private static int n;  // 노트의 세로 길이이자, 이름의 갯수
    private static int m;  // 노드의 가로 길이
    private static int[] names; // 적힐 이름의 갯수
    private static int[][] dp; // 적힐 이름의 갯수

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        names = new int[n + 1];
        dp = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            names[i] = Integer.parseInt(bf.readLine());
        }

        for (int i = 1; i <= n; i++)
            Arrays.fill(dp[i], Integer.MAX_VALUE);

        st = null;
        bf.close();

        System.out.println(getBlankCnt(1, 1, m + 1));
    }

    /*
    빈칸의 갯수를 출력하는 함수.
    이름을 적을 수 있는 경우의 수
    1. 옆에 이름을 젓는다.
        1. 빈칸이 있는 경우 적는다.
        2. break
    2. brank에 남은 빈칸의 제곱을 더한 다음에아래에 이름을젓는다.

    매개변수, 현재 이름의 위치, 현재 칸의 남은 빈칸의 갯수
     */
    private static int getBlankCnt(int pos, int line, int remain) {
        if (pos > n)
            return 0;
        // else
        if (remain >= names[pos] + 1) {
            dp[line][pos] = Math.min(dp[line][pos], getBlankCnt(pos + 1, line, remain - (names[pos] + 1)));
        }
        dp[line][pos] = Math.min(dp[line][pos], getBlankCnt(pos + 1, line + 1, m - names[pos]) + remain * remain);
        return dp[line][pos];
    }
}

댓글을 작성하려면 로그인해야 합니다.