[Python] 1783 병든 나이트 | 그리디 알고리즘

~실버 3~

 

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

1783번: 병든 나이트

 

[문제 해결 포인트]

1. 제한 사항을 단계적으로 분리하기

2. n의 제한 사항 이해하기

3. m의 제한 사항 이해하기

 

---

 

1. 제한 사항을 단계적으로 분리하기

처음에 문제를 읽으면 '... 뭐 어쩌라는 거야' 혹은 '이걸 어떻게 풀라는 거야'라는 생각을 할지도 모른다

내가 그랬다

 

다시 한번 문제를 찬찬히 살펴보고 제한 사항을 꼼꼼히 살펴보며침착하게 생각해 볼 필요가 있다.

 

모든 시작 위치는 (0, 0)이라고 가정한다.

 

입력으로 주어지는 n과 m의 크기에 따라 그 제한 사항이 결정되는데,

n(행 혹은 x축)은 3 이상만 되어도 2, 3번 움직임을 여러 번 사용할 수 있다.

(하지만 5회 이상시 조건에 위배되므로 최대 4번까지)

 

m(열 혹은 y축)은 나이트의 움직임에 반드시 포함되는 중요한 요소이다.

m의 크기 따라 최종 답이 결정되기 때문이다.

 

 

 

2. n의 제한 사항 이해하기

앞서 n의 크기에 따라 제한 사항이 결정된다고 했다.

어떻게 다를까?

 

1) n == 1이라면

아무리 m값이 크더라도 움직일 수 있는 방법이 없다.

그러므로 시작 위치 (0, 0)을 제외하면 방문한 칸은 없다.

 

if n == 1:
	print(1)

 

2) n == 2이라면

(0, 0)에서 3번 움직임 '1칸 아래로, 2칸 오른쪽'

(1, 2)에서 2번 움직임 '1칸 위로, 2칸 오른쪽'

......

 

m이 충분히 크다면(7 이상이면) 이렇게 2, 3번을 반복할 수 있을 것이다.

하지만 주의할 점은 방문한 위치가 5군데 이상이 되면 1~4조 건을 모두 만족해야 하는데,

해당 경우는 2, 3번만 만족했으므로 최대 4번까지 가능하다

물론 m이 충분히 크다는 조건에서 말이다.

 

m이 충분히 크지 않다면 2, 3조건은 항상 2씩 움직이므로

m//2번 움직일 수 있을 것이다.

처음 위치 (0, 0)을 더하는 것도 잊지 말자

 

if n == 2:
	print(min(4, (m-1)//2 + 1))

 

2) n == 3이라면

앞서 말했듯 n이 3 이상이라면 n에 대한 제한 사항은 더 이상 없다.

모든 1~4 움직임에서 위, 아래 조건을 만족시킬 수 있기 때문이다.

 

그렇다면 이제부터는 m의 크기에 따라 달라진다

 

 

 

3. m의 제한 사항 이해하기

n이 3 이상일 때를 가정하고 m의 제한 사항을 생각해야 한다.

n의 크기는 3 이상이기만 하면 아무리 커도 최종 크기에 영향을 줄 수 없다.

 

모든 움직임에는 오른쪽으로 가야 하는 제한 사항이 있고, 이를 최소화하는 것이

이 답의 핵심이기 때문이다.

 

1) m <= 6이라면?

이렇게 1칸 오른쪽 움직임을 포함하는 1, 4번으로 최대 움직임을 구할 수 있다!

이게 왜 최대냐면 2, 3번 움직임이 들어가는 순간 m의 제한된 크기를 허비하기 때문이다

 

최대한 오른쪽으로 덜 가는 방향이 핵심이다!

 

그런데 주의할 점은 모든 움직임을 만족하지 않는 이상 4 이상이 되면 안 된다는 것이다

 

else:
	if m <= 6:
		print(min(4, m))

 

2) m == 7이라면?

우리를 옭아매던 제한 사항이 모두 해방되었다!!

 

'n >= 3 and m == 7'인 경우인데,

모든 1~4 움직임을 커버할 수 있는 크기이기 때문에 7이어야만 했던 것이다.

모든 움직임을 커버하면 다음 같다.

동그라미 숫자 순서대로 살펴보면

3번 : 1칸 아래로, 2칸 오른쪽

2번 : 1칸 위로, 2칸 오른쪽

4번 : 2칸 아래로, 1칸 오른쪽

1번 : 2칸 위로, 1칸 오른쪽

 

모든 조건을 만족한 모습이다.

 

3) m > 7이라면?

m이 7일 때 조건에서 조금만 더 생각해 보면

오른쪽으로 가는 것을 최소화하는 것이 최대 움직임의 핵심이라는 것을 떠올릴 수 있다!

 

그러므로 모든 조건을 만족한 상태 이후는 움직임에 제한이 업으므로 m의 값을 따라

1, 4 움직임을 반복할 수 있게 된다.

 

즉, 7일 때 최댓값은 5

8일 때 최대값은 6

9일 때 최대값은 7

......

 

m-2가 최댓값이 된다.

 

	else:
		print(m-2)

 

 

 

 

 

<최종코드>

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

if n == 1:
    print(1)
elif n == 2:
    print(min(4, (m-1)//2 + 1))
elif m <= 6:
    print(min(4, m))
else:
    print(m-2)