[백준] 1757번 - 달려달려 (Gold 4)

문제 링크

백준 1757번 - 달려달려 (Gold 4)

문제 설명

다음 조건 하에서 N분동안 이동할 수 있는 거리의 최댓값을 구하시오.

1. i분부터 i+1분까지 1분간 달릴 경우 이동 거리는 $D_i$로 주어져 있다.
2. 1분동안 달리면 지침 지수가 1이 올라가며, 1분을 쉰다면 지침 지수가 1이 내려간다.
3. 지침 지수는 0 밑으로 떨어지지 않는다.
4. 지침 지수가 M보다 커질 수는 없다.
5. N분이 지났을 때 지침 지수는 0이어야 한다.
6. 달리다가 한번 쉬면 지침 지수가 0이 될때까지 다시 달릴 수 없다.

정답 코드 및 설명

마지막 1분 간 달리는지의 여부, 주어진 시간, 종료 시 지침 지수를 이용해서 점화식을 세워보자.
Dist[b][i][j]는 다음 조건 하에서의 이동할 수 있는 거리의 최댓값이다.

• 주어진 시간은 i+1분
• 종료 시 지침 지수는 j
• b = 0이면 마지막 1분(i분~i+1분) 동안 달리지 않는 경우이다.
• b = 1이면 마지막 1분 동안 달리는 경우이다.

1. Dist[0][i][j]
   • i분 시점에서의 지침 지수는 j+1
   • j = 0인 경우 i분 시점에서의 지침 지수가 0이어도 된다.
   • j = m인 경우는 불가능하다.
   • j > 0인 경우
     • $Dist[0][i][j] = \textrm{max}(Dist[0][i-1][j+1], Dist[1][i-1][j+1])$
   • j = 0인 경우
     • $Dist[0][i][j] = \textrm{max}(Dist[0][i-1][j+1], Dist[1][i-1][j+1], Dist[0][i-1][0])$
2. Dist[1][i][j]
   • i분 시점에서의 지침 지수는 j-1
   • j = 0인 경우는 불가능하다.
   • i-1분~i분까지 달리지 않았고 i분~i+1분까지 달린다면 i분 시점에서의 지침 지수가 0이어야 한다.
   • i-1분~i분까지 달린 경우 i분 시점에서의 지침 지수는 1 이상이다.
   • j = 1인 경우 i-1분~i분까지는 달릴 수 없다.
     • $Dist[1][i][j] = Dist[0][i-1][j-1] + D_i$
   • j > 1인 경우 i-1분~i분까지 무조건 달려야 한다.
     • $Dist[1][i][j] = Dist[1][i-1][j-1] + D_i$

코드로 구현하면 아래 코드와 같다.
아래 코드에서 maxDist[b][i][j]가 위 설명의 Dist[b][i][j]에 해당한다.

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

public class BOJ1757 {
    int n, m;
    int[] dist;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        dist = new int[n];
        for (int i = 0; i < n; i++)
            dist[i] = Integer.parseInt(br.readLine());
    }

    int maxDist() {
        // maxDist[0][i][j] : 마지막 i분때 안 달리고 지침지수 j로 끝남
        // maxDist[1][i][j] : 마지막 i분때 달리고 지침지수 j로 끝남
        int[][][] maxDist = new int[2][n][m + 1];
        maxDist[1][0][1] = dist[0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j < m) maxDist[0][i][j] = Math.max(maxDist[0][i - 1][j + 1], maxDist[1][i - 1][j + 1]);
                if (j == 0 && maxDist[0][i][0] < Math.max(maxDist[0][i - 1][0], maxDist[1][i - 1][0]))
                    maxDist[0][i][0] = Math.max(maxDist[0][i - 1][0], maxDist[1][i - 1][0]);
                if (j == 1) maxDist[1][i][j] = maxDist[0][i - 1][0] + dist[i];
                if (j > 1) maxDist[1][i][j] = maxDist[1][i - 1][j - 1] + dist[i];
            }
        }
        return maxDist[0][n - 1][0];
    }

    void solution() throws IOException {
        input();
        System.out.println(maxDist());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1757().solution();
    }
}