gyeongpyo   2년 전

이번 조 짜기 문제 풀면서

현재 i번까지의 최대값 = 이전 j번째 까지의 최대값 + j+1번째부터 i번째까지의 최대-최소 값 으로 생각해서 작성했었는데요.

코드를 계속바꾸다가 정답이 나오긴 했습니다.

밑에 소스코드는 정답이 나온 코드인데요.

오답이 떴었던 코드는 다음과 같습니다. (굵게 표시된 부분만 다릅니다.)

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (dp[i] < dp[j] + differ[j + 1][i])
                dp[i] = dp[j] + differ[j + 1][i];
        }
        if (dp[i] < differ[1][i])
            dp[i] = differ[1][i];
        if (dp[i] < dp[i - 1])
            dp[i] = dp[i - 1];
    }

우선 differ는 12 ~18에서 i~j번째 구간에서 최대-최소 값을 미리 저장해두었고,  i>j인경우에는 항상 0이 되기 때문에 위의 코드에서

j == i 일때

dp[i] < dp[j] + differ[j+1][i]

코드는

dp[i] < dp[i] + differ[i+1][i] 가 되므로 결국에는 dp[i] < dp[i]가 되기때문에

21번 줄 반복문 조건이 j<=i  이나 j <i이나 같게 되지 않나요?


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