shie44167   4달 전

일단 그리디 라는 도움을 받아서 열심히 규칙을 찾고 있었습니다.

case 1 홀홀 : 다 돌면 된다^^
case 2 홀짝, 짝홀 : 다 돌면 된다(짝수쪽으로 길게 움직여야)
case 3 짝짝 : 최대한 많이 간다 (다 돌 수가 없다)

이런 규칙을 나름 찾아서 문제를 풀었거든요

case 3은 숫자를 하나만 제외하고 다 돌 수 있어서 특정 위치의 숫자가 가장 작은지를 판단해서  6개의 case로 다시 나눌 수 있어서 그렇게 구현을 했지만 안되서 어디가 어떻게 틀렸는지 케이스나 지적 좀 부탁드립니다

ktjooho   4달 전

둘다 짝수인 경우에는 (R-1, C) 혹은 (R, C-1) 둘 중 하나가 빠지고, 나머지는 전부 방문가능한거죠?

shie44167   4달 전

둘 중 하난가요? (0, C), (R, 0)같은 부분만 빠질 수도 있지 않나요? 6가지 중 하나가 빠질수 있다고 생각했었는데

ktjooho   4달 전

아 다시 세어보니.. (1,2), (2,1) 도 빠질수있네요..(1,1)이 원점이라고 가정할 경우.

ktjooho   4달 전

아 제가 뭔가 잘못생각하고있는것같네요.. 

ktjooho   4달 전

둘다 짝수 인경우,  각 인덱스의 합이 홀수인 위치를 지나치는 경로를 다 그릴 수 있네요..

ktjooho   4달 전

예를 들어서 4*4 격자에서, (1,1)~ (4,4)일 경우에..

(1,2), (1,4), (2,1), (2,3), (3,2), (3,4), (4,1) , (4,3) 의 위치를 지나치면서, 나머지 위치를 지나는 경로를 만들 수 있네요.

n/2 개의 홀수가 나오는 인덱스 중에서 가장 작은 값을 지니는 인덱스를 지나치는 경로를 출력하면 되겠네요.

shie44167   4달 전

아 그렇군요. 잘 생각해보지 않았던 거네요 ㅎㅎ ㅠ

shie44167   4달 전

감사합니다 ^^

댓글을 작성하려면 로그인해야 합니다.