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`
- 2칸 위로, 1칸 오른쪽: (x - 2, y + 1)
- 1칸 위로, 2칸 오른쪽: (x - 1, y + 2)
- 1칸 아래로, 2칸 오른쪽: (x + 1, y + 2)
- 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
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[BOJ/DP] 백준 2193 - 이친수 (Java) (1) | 2025.06.01 |
---|---|
[BOJ/Greedy] 백준 1080 - 행렬 (Java) (1) | 2025.05.30 |
[BOJ/BFS] 백준 4963 - 섬의 개수 (Java) (1) | 2025.05.29 |
[BOJ/DFS] 백준 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 (Java) (0) | 2025.05.29 |
[BOJ/DP] 백준 11052 - 카드 구매하기 / 16194 - 카드 구매하기 2 (Java) (2) | 2025.05.28 |
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
- 2칸 위로, 1칸 오른쪽: (x - 2, y + 1)
- 1칸 위로, 2칸 오른쪽: (x - 1, y + 2)
- 1칸 아래로, 2칸 오른쪽: (x + 1, y + 2)
- 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
- 이동 4가지 모두 사용 ->
코드
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
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[BOJ/DP] 백준 2193 - 이친수 (Java) (1) | 2025.06.01 |
---|---|
[BOJ/Greedy] 백준 1080 - 행렬 (Java) (1) | 2025.05.30 |
[BOJ/BFS] 백준 4963 - 섬의 개수 (Java) (1) | 2025.05.29 |
[BOJ/DFS] 백준 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 (Java) (0) | 2025.05.29 |
[BOJ/DP] 백준 11052 - 카드 구매하기 / 16194 - 카드 구매하기 2 (Java) (2) | 2025.05.28 |