[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1783번, 병든 나이트

문제 링크

 

1783번: 병든 나이트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 병든 나이트가 이동하는 방법은 일반적인 나이트와 다르게 문제에 설명대로 움직입니다. 

2. 나이트의 시작 위치는 좌하단에서 시작합니다.

3. 나이트의 이동하는 횟수가 4번이상이면 최소 1번식 이동 방법을 사용해야합니다.

4. 나이트가 방문할 수 있는 최대 칸을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 체스판의 크기에 따라 최대로 이동할 수 있는 방법을 적용시킵니다.

 

3. 나이트가 방문할 수 있는 최대 칸을 결과로 출력합니다. 

 

 

병든 나이트 이동.

 

1. 2칸 위로, 1칸 오른쪽

2. 1칸 위로, 2칸 오른쪽

3. 1칸 아래로, 2칸 오른쪽

4. 2칸 아래로, 1칸 오른쪽

 

이동할 수 있는 경우

 

세로의 크기(N)가 1일 때

이동방법을 모두 사용할 수 없어서 처음 나이트가 있었던 1칸만 방문한 것으로 확인

방문한 칸 : 1칸

 

세로의 크기(N)가 2일 때

이동 방법 1과 4를 사용할 수 없어서 세로의 크기(M)에 따라 방문할 수 있는 칸이 달라집니다.

 

M > 7

이동 방법 1과 4만 쓰더라도 이동횟수를 4번이상 움직일 수 있습니다.

하지만 4번이상 움직인다면 이동방법 2, 3도 최소 1번은 사용해야하기 때문에 조건을 불만족합니다.

결과적으로 이동방법 1, 4를 최대 3번 쓰는 것이 최대의 칸으로 방문할 수 있습니다.

방문한 칸 : 4칸(초기 칸, 이동 방법 1과 4를 3번 써서 방문한 칸)

 

M ≤ 7

이동 방법 1과 4만 최대한 사용해도 4번 이상 사용이 불가능합니다.

시작 칸부터 이동방법 1과 4를 쓰면 2칸씩 늘어나기 때문에 홀수일 때 이동방법을 사용한 것입니다.

M이 짝수 : M/2칸 방문

M이 홀수 : (M/2 + 1)칸 방문

 

세로의 크기(N)가 3이상일 때

이동방법을 모두 사용할 수 있어서 세로의 크기(M)에 따라 방문할 수 있는 칸이 달라집니다.

 

M ≤ 4

이동방법을 4번 이상 사용할 수 없으므로 이동 방법 2, 3을 최대한 사용합니다.

이동방법 2, 3은 오른쪽으로 1칸씩 이동합니다.

방문한 칸 : M칸(초기 칸, 이동방법 2과 3을 M-1번 사용)

 

M ≤ 6

이동방법을 4번 이상 사용할 수 없으므로 이동 방법 2, 3을 3번 사용한 것이 최대 칸을 방문한 것입니다.

방문한 칸 : 4칸(초기 칸, 이동방법 2과3을 3번 사용)

 

M ≥ 7

이동한 방법을 4번 이상 사용할 수 있습니다.

최대의 칸을 방문하려면 이동방법 1, 4는 1번만 사용, 남은 가로의 길이를 이동방법 2, 3만 사용해서 이동을 진행합니다.

이동방법 1, 4는 오른쪽으로 2칸 이동하고, 이동방법 2, 3은 오른쪽으로 1개만 이동하기 때문입니다.

방문한 칸 : (M-2)칸(초기 칸, 이동방법 1과 4는 1번씩 이동, 남은 칸 이동방법 2와 3을 사용)

※ -2를 하는 이유는 이동방법 1, 4를 1번씩 사용하기 때문입니다.

 

예제입력 3.

1. 입력된 정보를 저장합니다.

 

N : 17

M : 5

 

 

2. 체스판의 크기에 따라 최대로 이동할 수 있는 방법을 적용시킵니다.

 

N의 크기는 3 이상!

M의 크기는 4 이상, 6  이하!

 

이동방법 2, 3을 3번 사용!

 

4칸 이동!

 

3. 나이트가 방문할 수 있는 최대 칸을 결과로 출력합니다. 

 

4칸을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 체스판의 정보를 띄어쓰기 기준 나누었습니다.
• 체스판의 가로와 세로 크기에 따른 방문한 칸을 계산하여 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    static int N, M;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        if(N == 1)		//세로의 크기가 1일 때
            bw.write( "1");
        else if(N==2){	//세로의 크기가 2일 때
            if(M>7)		//가로의 크기가 7보다 클 때
                bw.write("4");	//이동 횟수 1, 4을 3번 사용 : 4칸 방문
            else{		//가로의 크기가 7이하일 때
                //짝수와 홀수를 구분하여 방문한 칸 확인
                if(M%2==0)
                    bw.write(M/2 + "");
                else
                    bw.write((M/2+1) + "");
            }
        }else{		//세로의 크기가 3이상일 때
            if(M<=4)		//가로의 크기가 4이하일 때
                bw.write(M + "");	//초기칸 + 이동방법 2, 3 최대 사용 : M칸
            else if(M <= 6)	//가로의 크기가 6이하일 때
                bw.write( "4");	//초기칸 + 이동방법 2, 3을 3번 사용 : 4칸
            else{		//가로의 크기가 7이상일 때
                //초기칸 + 이동방법 1, 4을 1번 사용, 이동방법 2, 3 최대 사용 : M-2칸
                bw.write((M-2) + "");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}