백준(BOJ) 2873 : 롤러코스터 (JAVA)

문제링크 : https://www.acmicpc.net/problem/2873

2873번: 롤러코스터

필자가 싫어하는 그리디 유형이다...-_- 그리디 유형은 모든 경우의 수를 하나도 빠뜨림없이 고려하며, 각각의 경우의 수마다 규칙성을 찾고 그에 알맞게 코딩을 해야한다. 흐어... 그럼 설명을 시작해보도록 하겠다.

 

일단 연습장에 조금만 끄적여보다보면, 가로나 세로의 길이가 홀수일 경우, 모든 칸을 지나는 것이 가능하다는 것을 눈치챌 수 있을 것이다. 모든 칸을 지나갈 때의 점수보다 더 큰 점수를 만들 수는 없을 것이므로 이 때의 경로가 답이 된다. 그냥 지그재그로 움직이면 된다.

문제는 가로와 세로의 길이 모두 짝수일 때다. 이 때는 아무리 끄적거려봐도 모든 칸을 지나가는 것이 불가능하다. 조금 더 끄적거리다보면, 한 칸만 비워놓고 모든 칸을 지나가는 것은 가능하다는 것을 깨닫게 될 것이고, 빈 칸이 될 수 있는 칸은 아래 그림의 초록색 칸들이다.

초록색 칸은 i + j 가 홀수일 때다. 이 초록색 칸들 중에서 가장 낮은 점수를 가지고 있는 칸을 찾아서, 그 칸을 제외한 모든 칸을 지나가는 경로를 찾으면 점수가 최대인 경로를 얻게된다. 여기까지 생각해내는 건 쉽다. 이제 그 경로를 어떻게 찾아낼 수 있는지를 생각해내야하는데, 그게 좀 머리가 아프다...-_- 그 방법에 대해서는... 아래 코드를 보며 이해를 해보도록 하자^^;;;

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        
        if((r & 1) == 0 && (c & 1) == 0) {
            int minI = 0;
            int minJ = 0;
            int min = Integer.MAX_VALUE;
            
            for(int i = 0; i < r; i++) {
                st = new StringTokenizer(br.readLine());
                
                for(int j = 0; j < c; j++) {
                    if(((i + j) & 1) == 1) {
                        int n = Integer.parseInt(st.nextToken());
                        
                        if(min > n) {
                            min = n;
                            minI = i;
                            minJ = j;
                        }
                    } else {
                        st.nextToken();
                    }
                }
            }
            
            System.out.println(getAnswer(r, c, minI, minJ));
        } else {
            for(int i = 0; i < r; i++) {
                br.readLine();
            }
            
            if((r & 1) == 1) {
                System.out.println(getZigZag('R', 'L', 'D', c, r).deleteCharAt(r * c - 1));
            } else {
                System.out.println(getZigZag('D', 'U', 'R', r, c).deleteCharAt(r * c - 1));
            }
        }
    }
 
    private static String getAnswer(int r, int c, int minI, int minJ) {
        StringBuffer sb = new StringBuffer();
        int tmp = minI / 2 * 2;        
        sb.append(getZigZag('R', 'L', 'D', c, tmp));
        
        for(int i = 0; i < minJ; i++) {
            if((i & 1) == 0 ) {
                sb.append("DR");
            } else {
                sb.append("UR");
            }
        }
        
        for(int i = minJ; i < c - 1; i++) {
            if((i & 1) == 0 ) {
                sb.append("RD");
            } else {
                sb.append("RU");
            }
        }
        
        sb.append('D');
        sb.append(getZigZag('L', 'R', 'D', c, r - tmp - 2));
        
        return sb.deleteCharAt(sb.length() - 1).toString();
    }
 
    private static StringBuffer getZigZag(char f, char b, char d, int c, int r) {
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c - 1; j++) {
                if((i & 1) == 0) {
                    sb.append(f);
                } else {
                    sb.append(b);
                }
            }
            
            sb.append(d);
        }
        
        return sb;
    }
}