Greedy(14)_병든나이트(1783)

작성일 | In

BJO 1783 병든나이트

병든 나이트가 N*M의 체스판 가장 인쪽 아래 칸에 위치해있다. 네 가지만 움직일 수 있다.

  1. 위위 오른쪽
  2. 위, 오른쪽오른쪽
  3. 아래, 오른쪽오른쪽
  4. 아래아래, 오른쪽

이동 횟수가 4번 이상이면 위의 이동 방법을 각각 한번 이상 이용해야 한다

체스판의 크기가 주어졌을 때, 병든 나이트가 방문할 수 있는 칸의 최대 개수를 출력하는 프로그램을 작성( 처음에 있는 칸도 센다)

문제이해

N과 M이 2,000,000,000보다 작거나 같은 수라고 한다. 이는 하나씩 탐색하는 문제라는 게 아니란 것을 뜻한다.

나이트는 결국 오른쪽으로 밖에 이동할 수 없다. 최대로 반복한다면 이동하는 칸은 M이라는 것이다. (한칸씩만 이동하는 1과 4를 반복한다면,) 그런데 N이 2라면 무조건 오른쪽으로 2칸씩 밖에 못간다. 그럼 최대 칸은 M/2이다. 하지만 문제의 조건에서 이동 횟수가 4번 이상이면, 1~4번은 각각 한번씩은 해봐야 한다고 한다.

N = 1이면 항상 1이고 N=2라면 갈 수 있는 칸은 최대 4칸이다. 위 두가지를 제외하고는 N의 값은 상관 없다. 4회 이상을 이동할 수 있는 가로의 길이는 최소 7칸이다. 즉 4회 이상 이동하려면 2칸의 이상 손해를 봐야 한다.

정리히자면

N=1 -> 1 N=2 > 답(min(4,(m+1)/2)

  • 어차피 최대가 4이니까. 왜 m+1? m이 홀수 일 때 (m이 2면 이동x but m이 3이면 한 칸 이동 가능) 한칸 더 이동 가능하므로 N>2이면서 M<7이면 min(m,4)
  • M이 7보다 작으면 어떻게 되었든 최대 4회야. 이동 횟수가 4번 이상이면 1~4를 한번씩 해봐야 하기 떄문에 -2가 손해, 따라서 6일 때도 4칸이 최대.
  • N>2 이면서 그 외의 경우에는 m-2이다. (무조건 각각 한번씩 해줘야 하므로 2칸이 손해니까.)

문제를 정확히 이해하는게 중요하다.

코드


import sys

N, M = map(int, (sys.stdin.readline().split()))

if N == 1:
    print(1)
elif N == 2:
    print(min(4, (M+1)//2))
else:
    if(M < 7):
        print(min(M, 4))
    else:
        print(M-2)

참고자료 [참고한 블로그]https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221247616094&referrerCode=0&searchKeyword=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 [문제 이해 ]http://joonas-yoon.blogspot.com/2016/03/1783.html

0%