[Python] 1783. 병든 나이트(실3) /그리디

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

 

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

1783번: 병든 나이트

---

2. 핵심 아이디어

https://lipcoder.tistory.com/94

병든 나이트 (백준 - 1783번)

---

3. 코드

#1783. 병든나이트(실3)

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

if m<7 or n<3:

  flag=False

else:

  flag=True

result=1

if flag:

  result= m-2 #1칸에 하나씩 움직이는 것 가능 + 5칸까지는 1번씩 움직임

else:

  if n==1:

    result=1

  elif n==2:

    result= min(((m-1)//2)+1,4)

  elif m<7:

    result= min(m, 4)

print(result)

---

4.배운점

 

아직 그리디적인 사고가 유연하게 떠오르지 않는다. 그것이 많은 조건을 포함하고 있다면 더욱 그렇다.

구현 문제로 접근했다가 시간초과를 받았다. 범위가 넓은 문제의 경우, 그리디적으로 사고하는 법을 익히자.