99클럽 코테 스터디 10일차 TIL + 그리디

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

# 1783 병든 나이트

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

answer = 0
if n == 1:
    answer = 1
elif n == 2:
    answer = min(4, (m+1)//2) # 1 <= m <= 6 이면 (m+1)//2 m>6 이면 4
elif m <= 6: # n >= 3
    answer = min(4,m)
else:
    answer = m-2

print(answer)

 

• 우선 n >= 3 일 때부턴 elif로 위에서 걸러지기 때문에 m으로 조건문을 작성했다.
• 병든 나이트는 체스판 가장 왼쪽아래에서 출발하고 방문할 수 있는 칸의 최대 개수를 구해야 한다.
• 이동 횟수가 4 이상이면 4가지 이동 방법을 모두 한 번씩 사용해야한다.
• n == 1 이면 시작 칸 만 방문할 수 있다.
• n == 2 이면 세로로 한 칸씩만 움직일 수 있다.
  • 모든 이동 방법을 사용하지 못하므로 이동 횟수가 4번 이상 움직이지 못하므로 최댓값은 4이다.
• m <= 6 이면 모든 이동 방법을 사용하지 못하므로 최댓값은 4 , 오른쪽으로 한 칸씩 움직이면 되기 때문에 최솟값은 m이다.
• n >= 3 and m >= 7 이면 이동에 제약이 없고 오른쪽으로 2칸씩 이동하는 두가지 이동 방법을 한번씩 사용하는 것 외에 오른쪽으로 한칸씩 움직이면 되기 때문에 m-2 이 된다.

 

그리디 문제는 어떻게 풀어야 잘 푸는건지.. 해결 방법을 생각하는게 너무 어렵다 ㅜㅜ