백준 병든 나이트

 

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

📌 문제 요약

나이트가 체스판 위에서 이동할 수 있는데, 병들어서 **2가지 방향으로만 이동 가능**함.
단, 방문 횟수에 따라 **움직일 수 있는 방향 제약 조건**이 있음.

• 나이트는 총 4가지 방식으로 이동 가능 (실제론 2가지)
• 세로로는 위로만 이동함
• 총 이동 횟수에 따라 4가지 이동 방식 중 적어도 3가지 이상을 사용해야 제약이 풀림

📌 분기

• 높이 H가 1 → 움직일 수 없음 (정답: 1)
• H가 2 → 위로 2칸 못 가니까 최대 4번까지만 가능 (이동 방식 제한)
• H ≥ 3 and W < 7 → 이동 방향 4개 중 3개 이상 못 쓰니까 최대 W까지만
• 그 외에는 자유롭게 이동 가능 → W - 2칸까지 가능

💻 코드

n,m = map(int, input().split())
def solution(n, m):
    if n == 1:
        return 1
    elif n == 2:
        return min(4,(m + 1) // 2)
    elif m  < 7:
        return min(4, m)
    else:
        return m-2
print(solution(n,m))

📈 시간 복잡도

• O(1) - 조건 분기만 있기 때문에 입력 크기에 영향 없음

🧪 예제 확인

입력: 100 50
출력: 48