https://www.acmicpc.net/problem/1783
시간 1초, 메모리 128MB
input :
- N M (1 <= N, M <= 2,000,000,000)
output :
- 방문할 수 있는 칸의 개수중 최댓값을 출력
조건 :
-
가장 왼쪽아래 칸에 위치
-
2칸 위로, 1칸 오른쪽
-
1칸 위로, 2칸 오른쪽
-
1칸 아래로, 2칸 오른쪽
-
2칸 아래로, 1칸 오른쪽
-
병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
BFS로 풀고 있었는데... 영 아닌거 같아 다른 사람의 코드들을 찾아 보게 되었다.
다른 분들 모두 조건을 걸면서 하시는데 그림을 그려도 이해가 안되는 것이다..
결국 난 문제 이해를 잘 못 하고 있었다 ㅋㅋㅋㅋㅋㅋㅋ
나이트가 4번보다 적게 이동할 때는 위의 이동하는 방법을 아무렇게나 써도 상관 없지만..
그 보다 클 때는 위의 이동하는 방법을 모두 이용해야 한다.
아래 사이트의 풀이를 그려 놓으신걸 보고 알게 되었다... ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
https://sw-ko.tistory.com/155
세로가 1일 때는 시작하는 지점만,
세로가 2인 경우에는 2, 3 번의 이동하는 방법을 사용하는데 이 때 이동 가능 횟수는 3으로 최대 방문하는 지점은 (이동 가능 횟수 + 1) 이 된다.
1일 때는 1
3일 때 2
5일 때 3
7일 때 4
그 이후로 4 가 최대.
세로가 3이상인 경우에는 이동 가능 횟수가 3 까지 인 경우.
1이면 1
2이면 2
3이면 3
4, 5, 6이면 4
오른 쪽으로 1칸 움직이는 것으로 이동 가능 횟수 3회 사용.
아니면 그 이상이거나.
모든 이동하는 방법을 이용해서 움직 일 경우엔 가로의 길이가 7이상이여야 한다.
7일 때 5(이동 가능 횟수 4회 사용)
8일 때 6
9일 때 7
아 그리고 모두 한 번 씩 사용해야 한다는게 딱 한 번만 사용하고 그 다음부턴 또 상관이 없다는 거네 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 7이후에 8일 때 도 6 9일 때도 7 이 가능 한게 가로로 움직이는 거 1칸 짜리를 계속 쓴다는 것이네..... 레전드...
import sys
n, m = map(int, sys.stdin.readline().split())
ret = 1
if n == 2:
ret = min(4, (m + 1) // 2)
elif n >= 3:
if m <= 6:
ret = min(4, m)
else:
ret = m - 2
print(ret)
