[그리디] 백준 1783 병든 나이트

문제링크 www.acmicpc.net/problem/1783

 

 

[읽기 전에]

 

①

나이트가 이런식으로 이동했다면 3칸 방문한 것이다.

 

②

1, 2, 3, 4 이동 방법을 모두 한 번 씩 사용하고 난 후에는 1, 2, 3, 4 아무거나 사용해서 움직여도 가능하다

이동횟수가 4회째 되는 파란 화살표 이후 부분은 1, 4만 계속 이용해서 움직여도 무방하다

 

 

[답코드]

import sys
input=sys.stdin.readline
 
n, m=map(int, input().split())
#for문 안 써도 됨
 
if n==1:
    print(1)
elif n==2:
    print(min(4, (m + 1) // 2))
else:
    if m <= 6:
        print(min(4, m))
    else:
        print(m - 2)

 

[풀이법]

<이동 방법> 1. 2칸 위로, 1칸 오른쪽 2. 1칸 위로, 2칸 오른쪽 3. 1칸 아래로, 2칸 오른쪽 4. 2칸 아래로, 1칸 오른쪽

 

① n이 1일 때

나이트가 방문할 수 있는 칸은 1칸이다.

 

 

② n이 2일 때

n이 2개 이므로 전체 이동방법은 쓰지 못한다

이동 횟수가 4번보다 적을 때 이동방법에 제약이 없으므로 n이 2개일 때 최댓값은 4가 된다

 

m=1 일 때 1칸

m=2 일 때 1칸

m=3 일 때 2칸

m=4 일 때 2칸

m=5 일 때 3칸 방문이 가능하다

 

여기서 방문할 수 있는 칸의 수는 (m+1)//2를 통해 구할 수 있다

 

 

③ n이 3이상일 때

m이 6보다 작은 경우 최대 방문할 수 있는 칸의 수는 4이고

m이 3이면 3칸을 방문할 수도 있기 때문에 둘 중 최솟값을 출력한다

 

이동방법 4개를 모두 썼을 경우 1, 4만 계속 사용하며 움직이면 되기 때문에 이동한 칸의 수는 처음 2, 3을 이용하며 2칸씩 이동해 빈 칸의 수 2개만 빼주면 된다

 

 

 

작은 경우의 수부터 차례차례 분해해서 풀면 되는 문제였다

 

코테 스터디 하는데 다 건드시는 데 나만 손도 못대서 눈물이 났던 문제..^^

알고보니 문제 이해를 잘못했다

처음에는 이동하는 도중에 있는 칸까지 방문한 걸로 해석하고 풀었고, 그 다음에는 이동하면서 4가지 이동방법을 무조건 계속 써야하는 줄 알고 풀었다

 

정말 어려운 문제라고 생각했는데 문제 이해 잘 못한걸 바로 잡고보니 그렇게 어려운 문제는 아니었다.