[BOJ] 1783. 병든 나이트(그리디).java

#. Problem

www.acmicpc.net/problem/1783

* The copyright in this matter is in acmicpc

 

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

우선 N과 M은 "2,000,000,000보다 작거나 같은 자연수"라고 했으니 분명 생각이 필요한 문제다ㅋㅋㅋ

이동?!만 보고 탐색을 했다간... boooooom

 

움직일 수 있는 범위를 보니 무조건 오른쪽으로만 이동할 수 있고, 

무엇보다 "병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다." 이 문장이 모호했다.

 

4번보다 적은 경우 이동 방법에 대한 제약이 없다고 했는데, 5개 미만이라고 했는데... 4번 이동한 경우에 제약이 걸린다..

 

//

 

무조건 오른쪽으로 이동하니까 사실상 세로 길이에 규칙이 보일 것만 같다.

 

N = 1,

     이동이 불가능하다. 

     방문할 수 있는 칸은 1칸

 

N = 2,

     M = 1 : 1

     M = 2 : 1

     M = 3 : 2

     M = 4 : 2

     M = 5 : 3

     M = 6 : 3

     M = 7 : 4

     M = 8 : 4

     M = 9 : 4

     M = 10 : 4

     M = 11 : 4

     ...

     * 나누기 2의 반올림

     * 7보다 크면 무조건 4 (다른 이동 방법을 사용할 수 없음)

 

N = 3,

     M = 1 : 1

     M = 2 : 2

     M = 3 : 3

     M = 4 : 4

     M = 5 : 4

     M = 6 : 4

     M = 7 : 5

     M = 8 : 6

     M = 9 : 7

     M = 10 :8

     M = 11 :9

     ...

    * 6부터 M-2

 

N >= 3,    * 3부터는 지역이 세로로 넓어질 뿐 이동방향이 오른쪽으로 동일하다.

 

N = 3
ㅁ길ㅁㅁㅁㅁㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길
ㅁㅁㅁㅁ길ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
길ㅁ길ㅁㅁㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ

N =4
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
ㅁ길ㅁㅁㅁㅁㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길
ㅁㅁㅁㅁ길ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
길ㅁ길ㅁㅁㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ

N =5
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
ㅁ길ㅁㅁㅁㅁㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길
ㅁㅁㅁㅁ길ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
길ㅁ길ㅁㅁㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ길ㅁ
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ

 

#. Code

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

public class Main {

	static int N, M;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 가로
		M = Integer.parseInt(st.nextToken()); // 세로

		System.out.println(process());
	}

	public static int process() {
		if (N == 1) { // 이동 불가능
			return 1;
		} else if (N == 2) {
			// 7이상이면 무조건 4 (다른 이동방법을 사용할 수 없음)
			if (M < 7) return (M-1)/2 + 1; 
			else return 4;
		} else if (N >= 3) { // 3부터는 세로로 지역이 넓어질 뿐 이동방향은 동일
			if (M < 6) return Math.min(4, M);
			else return M - 2;
		}
		
		return 1;
	}
}