[백준(Baekjoon)][자바(java)] 1783 : 병든 나이트 / 그리디

 

www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

문제 풀이

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), 
		    m = Integer.parseInt( st.nextToken() );
		br.close();
		
		int c = 0;
		if( n == 1 ) 
			c = 1;
		else if( n == 2 ) 
			c = Math.min( 4, (m+1) / 2 );
		else {
			if( m <= 4 )
				c = m;
			else if( m <= 6 )
				c = 4;
			else
				c = m - 2;
		}
		
		System.out.println( c );
	}
}

 

*  그리디

-  세로 길이 : n, 가로 길이 : m
-  n = 1 ☞ m 상관없이 이동 불가능 ▶ c = 1
-  n = 2 ☞ 조건2, 3만 이동 가능 ▶ c = Math.min( 4, (m+1)/2 )
( 이동 횟수가 4이하여야 함. 이동 횟수가 4번보다 많으면 이동 방법을 모두 한 번씩 사용해야하기 때문 )
-  n >= 3 ☞ 조건 1, 2, 3, 4 모두 이동 가능
  -  m <= 4 ▶ c = m
  -  m <= 6 ▶ c = 4
  -  m > 6 ▶ c = m-2