[알고리즘] 병든 나이트

문제 링크

 

병든 나이트 : https://www.acmicpc.net/problem/1783

 

문제탐색

기본 원리 탐색

• • 체스에서의 나이트의 기본 이동반경을 4가지로만 제한하여 모든경우의 수 중 최대값을 구하는 문제입니다.
  • 문제를 이해하고 풀이법을 찾아가는 과정이 중요합니다.

 

시간복잡도와 알고리즘

• 시간제한 : 2초
  • 약 2억번의 연산이 가능하다고 가정합니다.
• N,M의 크기 : 20억 
  • 시간복잡도가 O(n) 인 알고리즘 조차도 20억을 넘어가며 시간초과가 나게 됩니다. 

즉 구현은 물론이며 반복을 한번이라도 사용할수 없는 문제이므로 해당 문제는 수학적인 수식으로 해결할 수 있는문제라고 판단할 수 있습니다.

 

=> 규칙을 찾고 수식으로 해결하는 그리디 해결법을 사용합니다.

 

코드설계하기

1. N과  M의 값을 입력받습니다.
2. 아래 규칙에 따라 조건문을 설계합니다.
3. #세로가 3이상 이며 가로값이 일정이상크면 = 가로값-2 
   #세로가 3이상 이며 가로가 5면 = 4
   #세로가 3이상 이며 가로가 4이하면 = 가로값
   #세로가 2이며 가로가 7 이상 이면 = 4
   #세로가 2이며 가로가 5,6이면 = 3
   #세로가 2이며 가로가 4,3이면 = 2
   #세로가 2이며 가로가 2 이하면 =1
   #세로가 1일때 = 1

 

시도회차 수정사항

• 1회차 : "세로가 2이며 가로가 7 이상 이면 = 4 "조건 누락
  • => 조건 추가

 

정답코드

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

if n>=3: #세로가 충분할때
    if m>=6:
        print(m-2)
    elif m==5: #가로가 5면 4
        print(4)
    else: #4이하면 가로값그대로
        print(m)
        
elif n==2: #세로가 2일때
    if m>=7: #가로가 7이상이면4
        print(4)
    elif m>=5 and m<7: #가로가 5이상이면 = 3
        print(3)
    elif m==4 or m==3: #가로가 4,3이면 = 2
        print(2)
    else: #가로가 2이하면 1
        print(1)
else: #세로가 1이면 1
    print(1)