[백준(Baekjoon)][자바(java)] 2873 : 롤러코스터 / 그리디

 

www.acmicpc.net/problem/2873

2873번: 롤러코스터

 

문제 풀이

 

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

public class Main {
	
	static StringBuilder path = new StringBuilder();
	static int r, c, r_e, c_e;  // row, column, row_expect, column_expect

	public static void zigzag_right() {
		char p;  int i, j;
		for( i = 0; i < r; i++ ) {
			p = i % 2 == 0 ? 'R' : 'L';
			for( j = 0; j < c-1; j++ )
				path.append( p ); 
			if( i != r-1 )  path.append( 'D' );
		}
	}
	
	public static void zigzag_down() {
		char p;  int i, j;
		for( i = 0; i < c; i++ ) {
			p = i % 2 == 0 ? 'D' : 'U';
			for( j = 0; j < r-1; j++ )
				path.append( p ); 
			if( i != c-1 )  path.append( 'R' );
		}
	}
	
	public static void zigzag_except_one() {
		int i;
		for( i = 0; i < r_e - 1; i += 2 ) {
			two_rows_all('r');
			path.append( 'D' );
		}
		two_rows_except_one();  
		for( i += 2; i < r - 1; i += 2 ) {
			path.append( 'D' );
			two_rows_all('l');
		}
	}
	
	public static void two_rows_all( char d ) {  // start direction -- right
		int i;
		char p1 = d == 'r' ? 'R' : 'L';
		char p2 = d == 'l' ? 'R' : 'L';
		for( i = 0; i < c-1; i++ )
			path.append( p1 );
		path.append( 'D' );
		for( i = 0; i < c-1; i++ )
			path.append( p2 );
	}
	
	public static void two_rows_except_one() {
		int i;
		for( i = 0; i < c_e - 1; i += 2 )
			path.append( "DRUR" );
		path.append( c_e % 2 == 0 ? "RD" : "DR" );
		for( i += 2; i < c - 1; i += 2 )
			path.append( "RURD" );
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		r = Integer.parseInt( st.nextToken() ); 
		c = Integer.parseInt( st.nextToken() );
		int a[][] = new int[r][c], min = Integer.MAX_VALUE, i, j;
		for( i = 0; i < r; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < c; j++ )
				a[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
		
		boolean re = ( r % 2 == 0 ), ce = ( c % 2 == 0 );  // r is even, c is even
		if( !re ) 
			zigzag_right();
		else if( re && !ce ) 
			zigzag_down();
		else if( re && ce ) {
			for( i = 0; i < r; i++ ) {
				for( j = 0; j < c; j++ ) {
					if( ((i%2==0)&&(j%2==1)) || ((i%2==1)&&(j%2==0)) ) {
						if( min > a[i][j] ) {
							min = a[i][j];
							r_e = i;
							c_e = j;
						}
					}
				}
			}
			zigzag_except_one();
		}
		System.out.println( path.toString() );
	}
}

 

*  그리디

 

세로 길이	가로 길이	방문 가능한 블록	경로
홀수	홀수	모든 블록	오른쪽/아래쪽 방향으로 지그재그
홀수	짝수	모든 블록	오른쪽 방향으로 지그재그
짝수	홀수	모든 블록	아래쪽 방향으로 지그재그
짝수	짝수	한 블록을 제외한 모든 블록	지그재그  <-- 여기가 관건

-  그 한 블록(★)은 체스판으로 따지면 검정 블록  ( 왼쪽 위(시작)와 오른쪽 아래(끝) 가 흰 블록인 체스판 )
 ( 인덱스가 세로(i)는 짝수, 가로(j)는 홀수인 경우 이거나 / 세로(i)는 홀수, 가로(j)는 짝수인 경우 )

-  가장 큰 기쁨을 주려면 제외할 한 블록은 기쁨 수치가 가장 낮은 것이어야 함
   검정 블록 중 기쁨 수치가 가장 낮은 지점( 행과 열 )을 구함

   ex) R = 4, C = 6

-  행을 2개씩 탐색하며 별이 없는 경우 2*N (ㄷ), 별이 있는 경우 2*2 (ㄱ) 로 케이스를 나눠서 생각