2021.2.10 [백준] 병든 나이트

그리디 알고리즘

 

 

Q

 

www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

A

 

경우의 수를 하나하나 생각하며 풀었다. 아마 시간제한이 있었다면 못풀었을 것이다.

주의해야 할 점은 4번 이동 전까지는 같은 방법을 여러번 써도 된다는 것이다.

 

코드

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

if n == 1:
    count = 1
elif n == 2:
    if m >= 7: #5번 이동부터는 같은 것 연속할 수 없어서 4로 제한
        count = 4 
    elif m >= 5:
        count = 3
    elif m >= 3:
        count = 2
    else:
        count = 1
else:
    if m >= 7: #각 방법 다 사용한 뒤에는 자유롭게 이동할 수 있으므로
        count = m - 2
    elif m >= 4:
        count = 4
    elif m == 3:
        count = 3
    elif m == 2:
        count = 2
    else:
        count = 1
    
print(count)