728x90
반응형

1783 - 병든 나이트

https://www.acmicpc.net/problem/1783

문제

병든 나이트가 N x M 크기 체스판의 가장 왼쪽아래 칸에 위치
4가지로만 움직일 수 있음
1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 함
이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 함
/ 4번보다 적은 경우(방문한 칸 < 5개): 이동 방법에 대한 제약 X

=> 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수?

입력: 체스판의 세로 길이 N, 가로 길이 M (N, M (자연수) <= 2,000,000,000)
출력: 여행에서 방문할 수 있는 칸의 개수 중 최댓값

풀이

  • 행 = 가로줄(row) = 세로 인덱스 (x)
  • 열 = 세로줄 (column) = 가로 인덱스 (y)

=> map[x][y]: x번째 줄의 y번째 칸

 

위로 이동: x - 1 / 아래로 이동: x + 1 / 왼쪽 이동: y - 1 / 오른쪽 이동: y + 1

  1. 2칸 위로, 1칸 오른쪽: (x - 2, y + 1)
  2. 1칸 위로, 2칸 오른쪽: (x - 1, y + 2)
  3. 1칸 아래로, 2칸 오른쪽: (x + 1, y + 2)
  4. 2칸 아래로, 1칸 오른쪽: (x + 2, y + 1) 

=> 모두 오른쪽(y) 증가, 세로(x)의 변화만 O = 오른쪽으로만 이동 O

 

  • N == 1 => 세로 1칸
    • x가 0 -> 위아래 이동 X 
    • 제자리만 방문 => 1
  • N == 2 => 세로 2칸
    • 2, 3번 방식만 가능 -> 2칸 오론쪽 이동, 위/아래 1칸 이동
    • 제한: 최대 4가지 이동방식을 모두 사용해야 4칸 이상 이동 가능
    • 방문 칸 수: min(4, (M + 1) / 2)
  • N >= 3 => 세로 3칸 (위/아래 총 3칸 이동)
    • 이동 4가지 모두 사용 -> M >= 7 (오른쪽으로 총 6칸 이동)
    • 방문 칸 수: M < 7 -> min(4, M) / M >= 7 -> M - 2

코드


      
import java.io.*;
import java.util.*;
// 병든 나이트
public class boj_1783 {
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());
int M = Integer.parseInt(st.nextToken());
int cnt = 0;
if (N == 1) cnt = 1;
else if (N == 2) {
cnt = Math.min(4, (M + 1) / 2);
} else {
if (M < 7) {
cnt = Math.min(4, M);
} else {
cnt = M - 2;
}
}
System.out.println(cnt);
}
}
728x90
반응형
kimmeoww