[그리디] Python - 1783번, 병든 나이트

www.acmicpc.net/problem/1783

import sys


def getMaxVisitable(N, M):
    if N == 1:
        return 1
    elif N == 2:
        return min(4, (M+1)//2)
    elif N >= 3:
        if M >= 7:
            return M-2
        else:
            return min(M, 4)


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

print(getMaxVisitable(N, M))

사실 문제는 어려운 편이 아니어서, 코드의 도출 과정을 설명하겠다.

우선, 'N과 M은 2,000,000,000보다 작거나 같은 자연수이다.'를 통해서 이 문제는 반복문을 쓰지 말고 계산식을 써야한다라고 말해주고 있는 것이다. 따라서 이것을 중점으로 문제를 탐색했다.

 

일단 N, M이 충분히 큰 때를 생각해보자. 위로 2칸 우로 1칸, 아래로 2칸 우로 1칸을 최대한 반복하여야 최댓값이 도출되며, 조건에 따라 위로 1칸 우로 2칸, 아래로 1칸 우로 2칸도 최소 1번은 진행해야한다. 따라서 이를 계산해보면, 'N>=3 And M>=7'일 때 M-2를 출력해야한다는 결과가 나온다.

아무튼 이렇게 가장 일반적이고 가장 큰 조건을 계산했으니, N, M을 좁혀가면서 패턴을 찾아낸다.

가로보다는 세로의 값에 따라 조건이 변하는 패턴을 찾기 쉬우므로 N>=3 / N==2 / N==1의 경우를 각각 분석해준다.

그 결과 코드는 아래와 같다.

하지만, 표를 그려보면 알겠지만 저렇게 일일히 따지지 않아도 코드를 획기적으로 줄일 수 있다. 그렇게 줄인 방안이 맨 위에 올린 코드이다.