백준 1783. 병든 나이트

🅰 백준 1783. 병든 나이트

1783번: 병든 나이트

✏️ 문제 풀이

• 이동횟수가 4번보다 적지 않다면 이동 방법을 모두 한 번씩 사용해야 한다는 조건이 있다. 
• 무조건 오른쪽으로만 이동할 수 있고 높이가 1,2,3일때로 구분을 해서 문제를 풀었다.
• 높이가 1일 때 : 한 칸도 이동할 수 없기 때문에 방문한 블록 : 1
• 높이가 2일 때
  • 가로가 8보다 작거나 같으면 (가로+1)/2 만큼 블록을 방문 가능
  • 가로가 8보다 크면 4가지 블록만 방문 가능
• 높이가 3일 때
  • 높이가 3이고 넓이가 7미만일 때(이동횟수가 4번보다 적을 때) : 넓이가 4보다 작으면 M만큼 이동, 그 외에는 4번 방문 출력
  • 높이가 3이고 넒이가 7이상일 때 : M-2만큼 이동 가능

✏️ 소스코드

package greedy;

/*
 * 백준 1783. 병든 나이트
 **/
import java.io.*;
import java.util.*;

public class Main_실버4_1783_손은성 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		// 높이가 1일 때 
		if (N == 1) {
			System.out.println(1);
		}
		// 높이가 2일 때
		else if (N == 2) {
			if (M <= 8)
				System.out.println((M+1)/2);
			else
				System.out.println(4);
		}
		// 높이가 3일 때
		else if (N >= 3) {
			// 높이가 3이고 넓이가 7 미만일 때
			if (M < 7) {
				if (M <= 4)
					System.out.println(M);
				else
					System.out.println(4);
			} 
			// 높이가 3이고 넓이가 7 이상일 때
			else {
				System.out.println(M - 2);
			}
		}
	}
}

 

✅ 후기

• 실버 4문제임에도 불구하고 생각하는데 어려움이 있어서 구글을 참고해서 풀었다. 그리디는 모든 경우의 수를 생각하고 조건을 잘 생각해서 구현하는게 중요하다고 느꼈다.