[Java] 단순한 동전 챙기기

문제 접근법 위 문제를 20분 정도 곰곰히 생각해봤을때, 모든 위치를 탐색해서 풀 수 있을것 같았다. 이를테면 start 위치의 좌표를 x,y라고 두었을때, 밑의 코드와 같이 백트래킹을 이용해 한칸씩 이동하고 특정 조건일때 가지를 쳐내는 방식으로 풀면 될 것 같았다. static void choose(int x, int y){ /* 조건 만족시 */ if(...) return; choose(x+1,y); choose(x,y+1); choose(x-1,y); choose(x,y-1); } 하지만 시간초과/메모리초과가 발생했고, 혼란스러워졌다. 시간초과를 해결하기 위해 가지치기 조건을 더 추가해야했는데, 문제를 살펴봤을때 더 이상 추가할 조건이 없었기 때문이다. visited 배열을 사용해서 방문한 곳은 더 이상 방문하지 않도록 만들어야하나 싶었지만, 문제에서 해당 위치를 지나가더라도 동전을 수집하지 않아도 되며 같은 위치를 2번 이상 지나가는 것 역시 허용라고 쓰여있어 그것도 아닌것 ...

원문링크 : [Java] 단순한 동전 챙기기