https://www.acmicpc.net/problem/2873
어려운문제는 아닌거같은데.
내가 접근한 방법은 가로,세로 길이중 하나라도 홀수라면 지그제그로 전부 방문 할 수 있고,
둘다 짝수일 경우 맨 마지막 위치의 위나 왼쪽값 둘중 하나만 선택이 가능하다. 따라서 둘 중 작은값은 버리고 큰값을 택한다.
(왼쪽값이 크다면 C-2까지 좌우지그제그로 갔다가, 그담부터는 위아래 지그제그로 내려가면 위쪽거 하나만 안먹고,
이것과 반대로하면 왼쪽거 하나만 안먹음)
라는식으로 접근했는데 틀렸다네. 뭐가 문제일까?
아 자문자답인데 밑에거 두개 먹는게 무조건 클 경우 위에것중에서 하나 버려야하는건가.
이게 그리디가 맞는건가 그리디라고해서 그리디로 풀라고하는데
둘다 짝수일때 가능한 경우가, 왼쪽가장아래,오른쪽가장위, 시작점오른쪽,시작점아래, 끝점 왼쪽,끝점위 이것들중에 하나를 안택하는게 맞나.
내일 질문하세여 그만 주무시고
시바 이거 그리디 맞나 내대가리로는 그리디가 아닌거같은데
저도 잠와서 자야함 내일한번봐봄
그리디 판별하려면 최적부분구조랑 또 뭐 하나 있었는데 그거 두개 증명하면 되지않나
ㅇㅇ 근데 이건 하나 확실히 맞는거같은게 한곳만 안가면 나머지 다 갈수 있으니까 하나만 택하면된다는거 근데 그 하나가 어떤 조건인지 모르겠네. 그것만 알면 풀릴거같은데