[자바] 백준 14550 - 마리오 파티 (java)

목차

문제 : boj14550

 

 

필요 알고리즘

• 다이나믹 프로그래밍 (DP, 동적 계획법)
  
  • 동적 계획법으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 '여러 줄에 걸쳐 N개의 정수가 주어진다.' 부분 때문에 입력 받는게 상당히 까다로울 수 있다. 자바로 어떻게 입력받아야할지 모르겠다면 이하 코드의 main 함수를 참고해보자. 내 경우 main에서 알아서 입력받은 뒤 solution 함수에 n, s, t, coin[] (각 칸의 코인) 을 넣어 각 문제를 해결하는 방식으로 처리했으며, 따라서 이하 풀이는 solution 함수 부분에 대해서만 다룬다. 

 

  dp[A][B] 를 A번 시도했을 때, B번 칸에 도달 시 획득 가능한 최대 코인수라 정의하자. A는 1부터 t, B는 1부터 n 까지의 범위를 가질꺼다. 참고로 코드에서는 dp[B] 로만 되어있는데, t번의 루프에서 매번 새로운 dp[B]를 생성하므로 (메모리를 줄이기 위해 이렇게 했다.) dp[A][B]로 처리하는 것과 동일하다. 이렇게 정의만 했다면 그뒤는 어떻게 해야 최대치를 찾을 수 있는지만 파악하면 된다. 어떻게 최대치를 찾는지는 이하에 주석으로 작성하였다.

private int solution(int n, int s, int t, int[] coin) throws Exception {
    int[] bf = new int[n+2];	// n+2인 이유는 인덱스 0은 Start, n+1은 End 지점으로 쓰기 위해서다.
    Arrays.fill(bf, NEGATIVE_INF);
    bf[0] = 0;	// Start 지점에서 시작 코인은 0이다.
    int answer = NEGATIVE_INF;

    while (t-->0) {	// 총 t번에 걸쳐서
        int[] dp = new int[n+2];	// 다음 dp를 진행한다. dp[A][B]에서 A를 증가시키는것과 동일하다.
        Arrays.fill(dp, NEGATIVE_INF);

        for (int i = 1; i <= n+1; i++) {	// 각 칸을 확인하면서
            for (int gap = 1; gap <= s; gap++) {	// 1부터 s까지 그 이전 값을 본다. dp[A-1][B-gap] 인 셈이다.
                if (i-gap < 0 || bf[i-gap] == NEGATIVE_INF) continue;	// 유효하지 않은 경우 패스

                dp[i] = Math.max(dp[i], bf[i-gap]+coin[i]);	// 이전 값 + 현재칸의 코인의 최대치를 찾으면 된다.
            }
        }
        answer = Math.max(answer, dp[n+1]);	// 총 t번 진행 이전에 답이 나올 수 있으므로 매번 최대치를 체크한다.
        bf = dp;
    }

    return answer;
}

 

 

 

코드 : github

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    static StringBuilder sb = new StringBuilder();
    static final int NEGATIVE_INF = -200*10000-1;

    public static void main(String[] args) throws Exception {
        while (true) {
            String str = br.readLine();
            if (str.charAt(0) == '0') break;

            StringTokenizer st = new StringTokenizer(str);
            int n = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            int[] coin = new int[n+2];
            int idx = 1;
            while (idx != n+1) {
                st = new StringTokenizer(br.readLine());
                while (st.hasMoreTokens()) coin[idx++] = Integer.parseInt(st.nextToken());
            }

            sb.append(new Main().solution(n, s, t, coin)).append('\n');
        }
        System.out.print(sb);
    }

    private int solution(int n, int s, int t, int[] coin) throws Exception {
        int[] bf = new int[n+2];
        Arrays.fill(bf, NEGATIVE_INF);
        bf[0] = 0;
        int answer = NEGATIVE_INF;

        while (t-->0) {
            int[] dp = new int[n+2];
            Arrays.fill(dp, NEGATIVE_INF);

            for (int i = 1; i <= n+1; i++) {
                for (int gap = 1; gap <= s; gap++) {
                    if (i-gap < 0 || bf[i-gap] == NEGATIVE_INF) continue;

                    dp[i] = Math.max(dp[i], bf[i-gap]+coin[i]);
                }
            }
            answer = Math.max(answer, dp[n+1]);
            bf = dp;
        }

        return answer;
    }
}