[Algorithm] 백준 1783 병든 나이트 | 그리디, 구현 (파이썬)

아이디어는 제대로 잡고 시작해서 엄청 금방 풀 거라고 생각했는데, 조건 하나를 잘못 생각하고 풀이하는 바람에 5번이나 틀리고 GPT에게 물어보고 나서야 해결했다는 사실... 

 

 

📝 백준 1783 병든 나이트

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

문제는 어렵지 않다! 나이트가 갈 수 있는 방향 4가지가 주어진다. 단, 이동 횟수가 4번 이상 되려면 4가지 방향을 한 번 이상씩 사용하고 나서 원하는 방향으로 갈 수 있다. 그리고 4번보다 적다면 한 방향으로 여러 번 갈 수 있다. 여기서 나이트가 갈 수 있는 최대 개수를 구하면 된다. (n: 높이, m: 너비)

나이트가 갈 수 있는 방향

 

💡 문제 풀이 아이디어

나이트는 →→↑, →→↓, →↑↑, →↓↓ 이렇게 4가지 방향으로 갈 수 있다. 즉, 우측으로만 이동할 수 있다는 의미다. 그렇다면 우측 방향으로 최소한만 이동하는 →↑↑, →↓↓ 이 두 가지 방법을 최대한 활용하면 된다. 그런데, →↑↑, →↓↓ 이 두 가지 방법은 세로 길이가 3칸 이상이어야만 자유롭게 쓸 수 있다. 그럼 1일 때, 2일 때는? 각각 나눠서 고려해 보자.

 

if n == 1:

세로 길이가 1이라면, 사실 어디든 갈 수 없다. 아무리 가로길이가 길더라도 현재 위치인 1칸만 방문할 수 있다.

 

if n == 2:

이제 →→↑, →→↓ 이 두 가지 방법을 이용할 수 있다. 그럼 가로로 얼마나 갈 수 있을지 계산하려면? 현재 위치를 제외하고, 2칸 이동할 수 있는 경우의 수를 계산하면 된다. ((m - 1) // 2) + 1. 마지막 1은 현재 위치. 물론 나누는 값이 2이기 때문에 (m + 1) // 2 로도 동일한 값이 나올 수 있지만, 만약 이동하는 거리가 2가 아니라면?이라는 생각으로 좀 더 의미에 맞게 그냥 ((m - 1) // 2) + 1 이렇게 두었다. 그리고 중요한 점, 4가지 방향을 모두 갈 수 없으니 최대로 방문할 수 있는 칸은 4칸이다. 둘 중에 더 작은 값을 사용해야 하므로, min(((m - 1) // 2) + 1. 4)가 된다.

 

if n >= 3:

이제 →↑↑, →↓↓ 이 두 가지 방향을 아주 자유롭게 갈 수 있다~

흠 4번 이상 이동하려면 모든 경우를 한 번 이상 적용해야 한다. 그럼 일단 적용해 보면 →→↑, →→↓, →↑↑, →↓↓ 이 네 가지 방향을 모두 적용할 때 필요한 칸은 3x7이다. 그럼 이동 횟수를 4번 이상으로 하려면, 가로 6칸은 필수로 지나가야 한다고 생각하고 마지막 말부터 새로운 여행을 떠난다고 볼 수 있다. 그럼 m < 7인 경우와 m >= 7 인 경우로 나누어 생각할 수 있다.

if n >= 3 and m < 7:

n >=3부터는 언급한 것처럼 →↑↑, →↓↓를 자유롭게 쓸 수 있다. 이 두 방향은 가로로 한 칸만 소모되므로, 방문한 칸의 수가 가로길이인 m이 된다. 다만, 이동 횟수를 4번 이상 가져갈 수 없기 때문에, min(m, 4)라고 할 수 있다.

if n >= 3 and m >= 7:

이제 모든 방향을 한 번씩 지나가고 난 경우이므로, 가로 6칸은 버리고 나머지 칸에서 이동할 수 있는 값을 계산하면 된다. (m - 6) + 4 = m - 2. 즉 빨간 네모 칸이 될 m - 6 만큼의 방문 횟수에서 4칸을 더하면 된다.

 

 

📝 문제 풀이 (파이썬)

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

if n == 1:
    print(1)
elif n == 2:
    print(min(4, ((m - 1) // 2) + 1))
""" 아래부터 n >= 3 """
elif m < 7:  # 여기서 m <= 7 이라고 해서 틀렸었다 🥲
    print(min(m, 4))
else:
    print(m - 2)

완료! 문제 아이디어만 잘 얻어내면 그렇게 어렵지 않았던 문제.. 조건 분기처리를 잘 보자..