코드업 4040 자바 - 펜션 (CodeUp 4040 java)

문제 : CodeUp4040

 

  어차피 중간에 하루라도 지낼 수 없다면 조건이 만족되지 않는다. 따라서 s부터 시작해서 매번 가장 길게 지낼 수 있는 방에서 지내면 된다. 그러다가 지낼 수 없는 날이 되면 -1, t 이상이 됬다면 변경 횟수를 출력하면 된다. 증명은 간단한데, 매번 가장 길게 지낼 수 있는 방이 아닌 다른 곳에 묵었을 때 더 이득이 되는 경우가 있다면 위의 추론이 틀린 것이다. 하지만 더 짧은 기간 지낼 수 있는 방을 고르더라도 동일한 변경횟수까진 나와서 더 낮은 변경 횟수가 될 수 없음은 직관적으로 알 수 있다. 따라서 그리디하게 선택하면 된다.

 

  그럼 해당하는 날에 어느 방이 가장 길게 묶을 수 있는 방인지 어떻게 알 수 있을까? 이건 날을 거꾸로 진행하면서 몇 일을 지낼 수 있는지 prefix sum 배열 만들듯이 세면 된다(단, X를 만났다면 0으로 초기화).

 

예를들어 입력 예시의 경우를 보자.

10 7
XXXXXXX
XOXXXXO
XOXXXXO
XOXXXOX
OXXOXOX
XOXOXOX
OXXOXOX
OXXXXOX
XXXXXXX
XXXXXXX
2 9

 

이 경우 위에서 말한 전처리 결과는 다음과 같다.

 

그럼 이제 s부터 t이상 진행하면서 현재 날 중 가장 높은 숫자를 고르면 된다. 가장 높은 수가 0일 경우 -1을 출력하고 끝내면 된다.

 

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j+1] = s.charAt(j) == 'O' ? 1 : 0;
            }
        }
        for (int i = n-1; i >= 1; i--) {
            for (int j = 1; j <= m; j++) {
                if (arr[i][j] == 0) continue;
                arr[i][j] += arr[i+1][j];
            }
        }

        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int total = 0;
        while (s<t) {
            total++;
            int max = 0;
            for (int j = 1; j <= m; j++) {
                max = Math.max(max, arr[s][j]);
            }
            if (max == 0) {
                System.out.println(-1);
                return;
            }
            s += max;
        }
        System.out.println(total-1);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}